Solution
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. This means that if we traverse the tree level by level, there should be no node after the first null node. If there is a node after the first null node while going level by level from left to right, it means that all the nodes are not as left as possible. Consider this graph:
1
/\
2 3
/ /\
4 5 6
Notice that first null node is encountered at the last level after 4. As all the nodes are not as left as possible, this is not a complete graph. This condition also ensures that all levels except possibly the last are completely filled. Consider that a level other than the last level is not completely filled. Now, the first null node is encountered at that level. Our condition says that there should be no node after the first encountered null node but in this case the next level is not empty, our condition is violated and hence it is not a complete binary tree.
Perform a level order traversal using a queue and keep adding nodes until an empty node is encountered in the queue. If the nodes are not as far left as possible, the queue will contain non-empty nodes. If all the nodes are as far left as possible but a node in level other than last level is empty then also the queue will contain the nodes of the next level. So all we then have to do is check if the queue contains a non-empty node.
bool isCompleteTree(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
while (q.front() != NULL) {
TreeNode* t = q.front();
q.pop();
q.push(t->left);
q.push(t->right);
}
// check if queue contains non-empty node
while (!q.empty()) {
TreeNode* t = q.front();
q.pop();
if (t != NULL)
return false;
}
return true;
}
Time complexity: O(n) where n is the no. of nodes