What is a Perfect Binary Tree?
A perfect Binary Tree is a binary tree in which each of the internal nodes has exactly two child nodes and all the leaf nodes are situated at the same level of the tree.
In other words, it can be said that each level of the tree is completely filled by the nodes.
Examples of Perfect Binary Tree:
Example of a Perfect Binary Tree
A tree with only the root node is also a perfect binary tree.
Example-2
The following tree is not a perfect binary tree because the last level of the tree is not completely filled.
Not a Perfect Binary Tree
Properties of a Perfect Binary Tree:
- Degree: The degree of a node of a tree is defined as the number of children of that node. All the internal nodes have a degree of 2. The leaf nodes of a perfect binary tree have a degree of 0.
- Number of leaf nodes: If the height of the perfect binary tree is h, then the number of leaf nodes will be 2h because the last level is completely filled.
- Depth of a node: Average depth of a node in a perfect binary tree is Θ(ln(n)).
- Relation between leaf nodes and non-leaf nodes: No. of leaf nodes = No. of non-leaf nodes +1.
- Total number of nodes: A tree of height h has total nodes = 2h+1 – 1. Each node of the tree is filled. So total number of nodes can be calculated as 20 + 21 + . . . + 2h = 2h+1 – 1.
- Height of the tree: The height of a perfect binary tree with N number of nodes = log(N + 1) – 1 = Θ(ln(n)). This can be calculated using the relation shown while calculating the total number of nodes in a perfect binary tree.
Check whether a tree is a Perfect Binary Tree or not:
- Find the depth of any node (in the below tree we find the depth of the leftmost node). Let this depth be d.
- Now recursively traverse the tree and check for the following two conditions.
- Every internal node should have both children non-empty.
- All leaves are at depth d
For more information about this refer to the article article: Check whether a given binary tree is perfect or not
