Full binary tree / Proper binary tree / 2-tree / Strictly binary tree):
Full Binary Tree is a tree in which every node other than the leaves has either 0 or 2 children.
so you have no leaves with only 1 child.
Here is an image of a full/strict binary tree,
Perfect Binary Tree:
Complete Binary Tree:
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and for Last level, and all nodes are as far left as possible.
What does above line mean A tree which follows a pattern like Root, Left child and Right child while creation of nodes till its last Node is complete binary tree,
If at any Level if Right child of a Node is Present without Left child then such a tree is not a Complete Binary Tree. For a Tree to be complete Binary Tree, It should have a Node, Left Child and a Right Child in sequence.
Full Binary Tree is a tree in which every node other than the leaves has either 0 or 2 children.
so you have no leaves with only 1 child.
Here is an image of a full/strict binary tree,
Perfect Binary Tree:
It is same as Full Binary tree with only difference as all Leaf Node of a Tree is at same Level. It means all the internal nodes must have 2 children.
Complete Binary Tree:
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and for Last level, and all nodes are as far left as possible.
What does above line mean A tree which follows a pattern like Root, Left child and Right child while creation of nodes till its last Node is complete binary tree,
If at any Level if Right child of a Node is Present without Left child then such a tree is not a Complete Binary Tree. For a Tree to be complete Binary Tree, It should have a Node, Left Child and a Right Child in sequence.
Lets look at example,
It is not a complete Binary Tree because it has not followed creation in Root node, Left child, Right child fashion at level 2(Node 5 left child is missing and right child is visible)
It is a complete Binary Tree because till last Node it Node J followed the creation of Root, left and right child.(It doesn't matter right child is not present for last Node. if right child is present for Node J and Left child is not present then it would not be a complete binary tree).
Remember, Tree having only Root Node is also a valid complete Binary Tree.
No comments:
Post a Comment