Complete Binary Tree vs Full Binary Tree
Binary tree is a tree where each node has one or two children. In a binary tree, a node cannot have more than two children. In a binary tree, children are named as “left” and “right” children. The child nodes contain a reference to their parent. A complete binary tree is a binary tree in which every level of the binary tree is completely filled except the last level. In the unfilled level, the nodes are attached starting from the left-most position. A full binary tree is a tree in which every node in the tree has two children except the leaves of the tree.
What is Full Binary Tree?
Full binary tree is a binary tree in which every node in the tree has exactly zero or two children. In other words, every node in the tree except the leaves has exactly two children. Figure 1 below depicts a full binary tree. In a full binary tree, the number of nodes (n), number of laves (l) and the number of internal nodes (i) is related in a special way such that if you know any one of them you can determine the other two values as follows:
1. If a full binary tree has i internal nodes:
– Number of leaves l = i+1
– Total number of nodes n = 2*i+1
2. If a full binary tree has n nodes:
– Number of internal nodes i = (n-1)/2
– Number of leaves l=(n+1)/2
3. If a full binary tree has l leaves:
– Total Number of nodes n=2*l-1
– Number of internal nodes i = l-1
What is Complete Binary Tree?
As shown in figure 2, a complete binary tree is a binary tree in which every level of the tree is completely filled except the last level. Also, in the last level, nodes should be attached starting from the left-most position. A complete binary tree of height h satisfies the following conditions:
– From the root node, the level above last level represents a full binary tree of height h-1
– One or more nodes in last level may have 0 or 1 children
– If a, b are two nodes in the level above the last level, then a has more children than b if and only if a is situated left of b
What is the difference between Complete Binary Tree and Full Binary Tree?
Complete binary trees and full binary trees have a clear difference. While a full binary tree is a binary tree in which every node has zero or two children, a complete binary tree is a binary tree in which every level of the binary tree is completely filled except the last level. Some special data structures like heaps need to be complete binary trees while they don’t need to be full binary trees. In a full binary tree, if you know the number of total nodes or the number of laves or the number of internal nodes, you can find the other two very easily. But a complete binary tree does not have a special property relating theses three attributes.
Thanks