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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // Function to check if given Binary Tree is Complete or not bool isComplete(Node* root) { // return if tree is empty if (root == nullptr) return false; // create an empty queue and enqueue root node list<Node*> queue; queue.push_back(root); // pointer to store current node Node* front = nullptr; // flag to mark end of full nodes bool flag = false; // run till queue is not empty while (queue.size()) { // pop front node from the queue front = queue.front(); queue.pop_front(); // if we have encountered a non-full node before and current node // is not a leaf, tree cannot be complete tree if (flag && (front->left || front->right)) return false; // if left child is empty and right child exists, binary // tree cannot be complete if (front->left == nullptr && front->right) return false; // if left child exists, enqueue it if (front->left) queue.push_back(front->left); // if current node is a non-full node, set flag to true else flag = true; // if right child exists, enqueue it if (front->right) queue.push_back(front->right); // if current node is a non-full node, set flag to true else flag = true; } return true; } |

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // Perform in-order traversal of the array and fill array A[] void inorder(Node* root, vector<bool> &A, int i) { if (root == nullptr) return; // recurse with index 2i+1 for left node inorder(root->left, A, 2*i + 1); // mark index i as visited A[i] = true; // recurse with index 2i+2 for right node inorder(root->right, A, 2*i + 2); } // Function to check if given binary tree is complete binary tree or not // call as isComplete(root, n) where n is number of nodes in the tree bool isComplete(Node* root, int n) { // return if tree is empty if (root == nullptr) return true; // construct an auxiliary boolean array of size n vector<bool> A(n, false); // fill array A[] inorder(root, A, 0); // check if all positions in the array are filled or not for (int i = 0; i < n; i++) if (!A[i]) return false; return true; } |

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // Recursive function to check if given binary tree is complete tree or not // call as isComplete(root, 0, n) where n is number of nodes in the tree bool isComplete(Node* root, int i, int n) { // return if tree is empty if (root == nullptr) return true; if ((root->left && 2*i + 1 >= n) || !isComplete(root->left, 2*i + 1, n)) return false; if ((root->right && 2*i + 2 >= n) || !isComplete(root->right, 2*i + 2, n)) return false; return true; } |

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 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 🙂

## Leave a Reply

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.

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[0]){

// Has a left child but no right child

if(root.left != null && root.right == null)

flag[0] = 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*/

Mohan,

Thank you for liking Techie Delight.

If we’re not wrong, you’re checking only last two levels of the binary tree. Violation can happen at the top as well.