# 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 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 –

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. C++ implementation –

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. C++ implementation –

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.     (1 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest

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. Guest

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); } private boolean isCompleteRecursive(TreeNode root, int height, int level, boolean[] flag) { if(root == null) { if(level < height) // Handles halfNodes before last level return false; return true; } // This case needs to be handled separately and not combined with below case. // Exception : Right Height is more than left height and all nodes till now are complete if(level == height) { if(root.left == null && root.right == null) return true; else //Handles nodes who aren't leaves return false; } if(level == height - 1) { if(!flag){ // Has a left child but no right child if(root.left != null && root.right == null) flag = true; } else { // All other nodes in this level should have no children if(root.left == null && root.right == null) return true; else return false; } } return isCompleteRecursive(root.left, height, level+1, flag) && isCompleteRecursive(root.right, height, level+1, flag); } /*Code Ends*/```