Given a Binary Tree, write a function to check whether the given Binary Tree is a prefect Binary Tree or not.
A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at same level.
The following tree is a perfect binary tree
10 / 20 30 / / 40 50 60 70 18 / 15 30
The following tree is not a perfect binary tree
1 / 2 3 / 4 5 6
A Perfect Binary Tree of height h (where height is number of nodes on path from root to leaf) has 2h – 1 nodes.
Below is an idea to check whether a given Binary Tree is perfect or not.
- Find depth of any node (in below tree we find depth of leftmost node). Let this depth be d.
- Now recursively traverse the tree and check for following two conditions.
- Every internal node should have both children non-empty
- All leaves are at depth ‘d’
Time complexity : O(n)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.