Problem

Given the root of a binary tree, determine if it is a complete binary tree.

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. It can have between 1 and 2h nodes inclusive at the last level h.

Examples

Example 1:

graph TD
	1 --- 2 & 3
	2 --- 4 & 5
	3 --- 6
	3 ~~~ N1:::hidden

classDef hidden display:none
  
1
2
3

Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Example 2:

graph TD
	1 --- 2 & 3
	2 --- 4 & 5
	3 ~~~ N1:::hidden
	3 --- 7
classDef hidden display:none	
  
1
2
3

Input: root = [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.

Solution

Method 1 - Using Level order Traversal

A complete binary tree satisfies two conditions:

  • Every level, except possibly the last, is completely filled.
  • All nodes at the last level are as far left as possible.

Here is the approach:

  • Traverse the binary tree level by level using Breadth First Search (BFS) (i.e., a queue).
  • While traversing, ensure that no null node comes before a non-null node. If a null node appears and there’s a non-null node later, it is not a complete binary tree.
  • If the traversal ends without finding such irregularities, then the given binary tree is complete.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        
        q = deque([root])
        found_null = False
        
        while q:
            node = q.popleft()
            if node:
                if found_null:  # If a null node was found earlier, the tree is not complete
                    return False
                q.append(node.left)
                q.append(node.right)
            else:
                found_null = True  # Mark that a null node has been encountered
        
        return True
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) return true;
        
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        boolean foundNull = false;
        
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node != null) {
                if (foundNull) {
                    return false; // If a null node was encountered earlier and this is non-null
                }
                q.offer(node.left);
                q.offer(node.right);
            } else {
                foundNull = true; // Mark that a null node was encountered
            }
        }
        
        return true;
    }
}

Complexity

  • Time: O(n) where n is the number of nodes, as we visit each node once during BFS traversal.
  • Space:  O(n) for the queue used in BFS, as in the worst case, the last level nodes are stored in the queue.