Check if given binary tree is complete binary tree or not

Given a binary tree, check if it is a complete binary tree or not.

 

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.

For example, below binary trees are complete

complete-binary-tree

 


 
Approach 1: Level Order Traversal (BFS)
 

We can modify level order traversal to check if given binary tree is complete binary tree or not. The idea is for every dequeued node, we check if it is full node (have both left and right children). If we found a node that is not a full node i.e either it has no children or only 1 child, then all the remaining nodes in the queue should not have any children. If anyone of them has a child then its not complete binary tree else it is.

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 


 

Approach 2: Array representation of complete tree
 

We can solve this problem by using properties of a complete binary tree. We know that in array representation of binary tree, the left child for a node at index i is present at index 2i+1 and right child is present at index 2i+2. If we construct an array with all the elements in the tree at the corresponding positions, then for a complete binary tree, the elements will hold consecutive positions. If any vacant position is found, then tree cannot be a complete tree.

complete-binary-trees

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 


 

Approach 3: Space Optimized previous approach
 

Above approach takes extra space for storage of boolean array. As discussed for a complete binary tree, the index of left and right child for any node is less than number of nodes for every node. We can avoid using extra space by passing index as a parameter in recursion and check for every node that their left and right child’s index are within correct range.

array-complete-tree

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Mohan
Guest
Mohan
Hi, I found your blog very useful. I have thought of below approach for this question. Request you to take a look. /* Code starts*/ public void isCompleteRecursive() { if(root != null) { int leftHeight = heightRecursive(root.left); boolean[] flag = {false}; boolean isComplete = isCompleteRecursive(root, leftHeight, 0, flag); } System.out.println(isComplete);… Read more »
Andrew
Guest
Andrew

In Approach 2 – line 18 (“A[i] = true;”), you imply that accessing of the vector A at index i is not bound-checked. This work for std::vector as std::vector::operator[] ignores indices that are out of range; however, it will crash for C-style array.

wpDiscuz