Difference between "Complete binary tree", "strict binary tree","full binary Tree"?
Perfect Tree:
x
/ \
/ \
x x
/ \ / \
x x x x
/ \ / \ / \ / \
x x x x x x x x
Complete Tree:
x
/ \
/ \
x x
/ \ / \
x x x x
/ \ /
x x x
Strict/Full Tree:
x
/ \
/ \
x x
/ \
x x
/ \
x x
Wikipedia yielded
A full binary tree (sometimes proper binary tree or 2-tree or strictly binary tree) is a tree in which every node other than the leaves has two children.
So you have no nodes with only 1 child. Appears to be the same as strict binary tree.
Here is an image of a full/strict binary tree, from google:
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
It seems to mean a balanced tree.
Here is an image of a complete binary tree, from google, full tree part of image is bonus.
There is a difference between a STRICT and FULL BINARY TREE.
1) FULL BINARY TREE: A binary tree of height h that contains exactly (2^h)-1 elements is called a full binary tree. (Ref: Pg 427, Data Structures, Algorithms and Applications in C++ [University Press], Second Edition by Sartaj Sahni).
or in other words
In a FULL BINARY TREE each node has exactly 0 or 2 children and all leaf nodes are on the same level.
For Example: The following is a FULL BINARY TREE:
18
/ \
15 30
/ \ / \
40 50 100 40
2) STRICT BINARY TREE: Each node has exactly 0 or 2 children.
For example: The following is a STRICT BINARY TREE:
18
/ \
15 30
/ \
40 50
I think there's no confusion in the definition of a Complete Binary Tree, still for the completeness of the post I would like to tell what a Complete Binary Tree is.
3) COMPLETE BINARY TREE: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible.
For Example: The following is a COMPLETE BINARY TREE:
18
/ \
15 30
/ \ / \
40 50 100 40
/ \ /
8 7 9
Note: The following is also a Complete Binary Tree:
18
/ \
15 30
/ \ / \
40 50 100 40