Problem Description

You need to determine if a given binary tree is a complete binary tree.

A complete binary tree has the following properties:

• Every level is completely filled with nodes, except possibly the last level
• The last level must be filled from left to right without any gaps
• If the last level is not full, all nodes must be positioned as far left as possible

For example:

• A tree with nodes arranged like [1, 2, 3, 4, 5] where nodes 4 and 5 are children of node 2 would be complete
• A tree with nodes arranged like [1, 2, 3, null, null, 4] where node 4 is the left child of node 3 would be complete
• A tree with nodes arranged like [1, 2, 3, 4, null, null, 5] would NOT be complete because there's a gap (node 2 has no right child while node 3 has a child)

The solution uses a level-order traversal (BFS) approach. It processes nodes level by level using a queue. When it encounters the first None node, it stops adding nodes to the queue. After this point, if there are any non-None nodes remaining in the queue, the tree is not complete. If all remaining nodes are None, the tree is complete.

The key insight is that in a complete binary tree, once you encounter a None node during level-order traversal, all subsequent nodes must also be None. Any non-None node after a None indicates a gap in the tree structure, violating the complete binary tree property.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph (specifically, a connected acyclic graph).

Is it a tree?

• Yes: The problem explicitly deals with a binary tree structure.

DFS?

• Not necessarily: While DFS could work, the problem requires checking level-by-level completeness. We need to verify that all levels are filled from left to right, which is more naturally suited to level-order traversal (BFS). The solution needs to detect gaps in the tree structure by processing nodes level by level.

Let's reconsider the path through the flowchart:

Since we need level-order traversal to check completeness (processing nodes level by level from left to right), and the flowchart paths from "tree" lead to DFS, we should note that for this specific tree problem, BFS is the optimal choice even though it's not the default tree traversal suggested by the flowchart.

The key insight is that checking for completeness requires:

1. Processing nodes in level order (left to right)
2. Detecting when we encounter the first None node
3. Verifying no non-None nodes appear after the first None

This pattern perfectly aligns with BFS traversal using a queue, where we can naturally process nodes level by level and detect gaps in the tree structure.

Conclusion: The flowchart would typically suggest DFS for tree problems, but the specific requirement of checking completeness (which involves level-order properties) makes BFS (Breadth-First Search) the ideal approach for this problem.

Intuition

The key insight for checking if a binary tree is complete comes from understanding what happens during a level-order traversal of a complete vs. incomplete tree.

In a complete binary tree, when we traverse level by level from left to right, all non-null nodes appear consecutively at the beginning, followed by all null nodes at the end. There's never a situation where we see a null node followed by a non-null node.

Think about it this way: imagine pouring water into a tree structure level by level, from left to right. In a complete tree, the water fills continuously without leaving any gaps. The moment we encounter an empty spot (null node), everything after it must also be empty.

This observation leads to a simple algorithm:

1. Use BFS to traverse the tree level by level
2. Add all nodes to the queue, including None children
3. When we encounter the first None node, stop the traversal
4. Check if any non-None nodes remain in the queue

If there are non-None nodes after we've seen a None, it means there's a gap in our tree structure - violating the complete binary tree property. For example, if node 2 has no right child but node 3 (at the same level) has children, we'd encounter None from node 2's missing child, then later see node 3's children in the queue.

The beauty of this approach is that we don't need to track levels, positions, or do complex calculations. We simply rely on the fact that in a complete tree, once we see a "hole" (null node) during level-order traversal, everything else must be a hole too.

Learn more about Tree, Breadth-First Search and Binary Tree patterns.

Solution Approach

The implementation uses a BFS (Breadth-First Search) approach with a queue data structure to traverse the tree level by level.

Here's the step-by-step walkthrough of the algorithm:

1. Initialize the Queue: Start with a deque containing the root node.

   q = deque([root])

2. Process Nodes Until First None: Use a while loop to process nodes from the queue:

   while q:
       node = q.popleft()
       if node is None:
           break
       q.append(node.left)
       q.append(node.right)

   • Remove the first node from the queue
   • If it's None, immediately break out of the loop
   • If it's a valid node, add both its children to the queue (even if they are None)

3. Check Remaining Queue: After breaking from the loop (when we encounter the first None), check if all remaining elements in the queue are None:

   return all(node is None for node in q)

   • If all remaining nodes are None, the tree is complete
   • If any non-None node exists, the tree is not complete

The algorithm's correctness relies on a crucial property: in a complete binary tree's level-order traversal, all None nodes must appear after all non-None nodes. Any violation of this pattern indicates an incomplete tree.

Time Complexity: O(n) where n is the number of nodes, as we visit each node at most once.

Space Complexity: O(w) where w is the maximum width of the tree, which in the worst case (complete tree) is O(n/2) = O(n) for the last level.

Example Walkthrough

Let's walk through the algorithm with a concrete example to see how it identifies whether a tree is complete.

Example Tree:

       1
      / \
     2   3
    / \
   4   5

This tree should be complete. Let's trace through the algorithm:

Step 1: Initialize

• Queue: [1]

Step 2: Process node 1

• Pop node 1 from queue
• Node 1 is not None, so add its children
• Queue: [2, 3]

Step 3: Process node 2

• Pop node 2 from queue
• Node 2 is not None, so add its children
• Queue: [3, 4, 5]

Step 4: Process node 3

• Pop node 3 from queue
• Node 3 is not None, so add its children (both None)
• Queue: [4, 5, None, None]

Step 5: Process node 4

• Pop node 4 from queue
• Node 4 is not None, so add its children (both None)
• Queue: [5, None, None, None, None]

Step 6: Process node 5

• Pop node 5 from queue
• Node 5 is not None, so add its children (both None)
• Queue: [None, None, None, None, None, None]

Step 7: Encounter first None

• Pop first None from queue
• Break from the while loop
• Queue still contains: [None, None, None, None, None]

Step 8: Check remaining queue

• All remaining elements are None
• Return True - the tree is complete!

Counter-example (Incomplete Tree):

       1
      / \
     2   3
      \   \
       5   6

Following the same process:

• After processing nodes 1, 2, and 3, queue would be: [None, 5, None, 6]
• When we pop the first None and break
• Queue contains: [5, None, 6]
• Since there are non-None nodes (5 and 6) after we encountered a None, return False

The key insight: the presence of nodes 5 and 6 after a None indicates gaps in the tree structure, violating the complete binary tree property.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the binary tree.

The algorithm uses BFS (Breadth-First Search) to traverse the tree level by level. Each node in the tree is visited exactly once when it's dequeued from the queue. After encountering the first None value, the algorithm performs one more linear scan through the remaining elements in the queue using the all() function. In the worst case (a complete tree), all nodes are processed before encountering None, and the queue will contain at most O(n) None values to check. Therefore, the total time complexity is O(n) + O(n) = O(n).

Space Complexity: O(n) where n is the number of nodes in the binary tree.

The space complexity is determined by the maximum size of the queue during execution. In a complete binary tree, the maximum number of nodes at any level is at the last level, which can contain up to n/2 nodes. Additionally, when we reach the first None, the queue might contain both actual nodes and None values from the last level. In the worst case, the queue can hold up to O(n) elements (considering both node references and None values), making the space complexity O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly Stopping at First None Child

A common mistake is to stop the traversal as soon as a node has a None child, rather than continuing to process until a None node is actually dequeued.

Incorrect Implementation:

def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
    queue = deque([root])
  
    while queue:
        current_node = queue.popleft()
      
        # WRONG: Checking children for None before processing
        if current_node.left is None or current_node.right is None:
            # This would incorrectly reject valid complete trees
            # where the last level isn't full
            break
          
        queue.append(current_node.left)
        queue.append(current_node.right)
  
    return all(node is None for node in queue)

Why it's wrong: This approach would incorrectly classify trees like [1, 2, 3, 4] as incomplete, even though they are valid complete binary trees.

Pitfall 2: Not Adding None Children to Queue

Another mistake is skipping None children when adding to the queue, which breaks the level-order position tracking.

Incorrect Implementation:

def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
    queue = deque([root])
  
    while queue:
        current_node = queue.popleft()
        if current_node is None:
            break
      
        # WRONG: Only adding non-None children
        if current_node.left:
            queue.append(current_node.left)
        if current_node.right:
            queue.append(current_node.right)
  
    return all(node is None for node in queue)

Why it's wrong: By not adding None nodes to the queue, we lose the positional information needed to detect gaps. For example, a tree like [1, 2, 3, null, null, 4] would incorrectly be classified as incomplete because we'd never encounter the None nodes between node 2's children and node 3's left child.

Pitfall 3: Using a Flag-Based Approach Incorrectly

Some might try to use a boolean flag to track whether a None has been seen, but implement it incorrectly.

Incorrect Implementation:

def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
    queue = deque([root])
    seen_none = False
  
    while queue:
        current_node = queue.popleft()
      
        if current_node is None:
            seen_none = True
            continue
      
        # WRONG: Not checking the flag before adding children
        if seen_none:
            return False
          
        queue.append(current_node.left)
        queue.append(current_node.right)
  
    return True

Why it's wrong: This checks the flag too late. Once we've seen a None, we shouldn't process any more non-None nodes at all. The check should happen immediately after dequeuing.

Correct Solution Reminder

The correct approach:

1. Add ALL children (including None) to the queue
2. Break immediately when dequeuing a None node
3. Check that all remaining queued nodes are None

This ensures we properly detect any gaps in the tree structure while correctly handling valid complete trees where the last level isn't full.