Check Completeness of a Binary Tree: BFS Level-Order Validation

Given the root of a binary tree, determine if it is a complete binary tree. A complete binary tree has every level fully filled except possibly the last, where all nodes are as far left as possible. This is LeetCode 958: Check Completeness of a Binary Tree.

For example, given root = [1, 2, 3, 4, 5, 6], the answer is True. Every level is packed left to right with no gaps. But given root = [1, 2, 3, 4, 5, null, 7], the answer is False because node 3 has no left child yet has a right child, creating a gap in the level-order sequence.

Approach: BFS with null tracking

The key insight is simple. If you run BFS (level-order traversal) and push every child into the queue, including null children, then a complete binary tree produces a sequence where all the non-null nodes come first, followed by all the null nodes. There are no gaps.

An incomplete tree, on the other hand, has at least one null node followed by a non-null node somewhere in that BFS sequence. That is the gap you need to detect.

So the algorithm is:

1. Push the root into a queue.
2. Dequeue nodes one at a time.
3. If the node is null, set a flag (seen_null = True).
4. If the node is non-null but you have already seen a null, the tree is incomplete. Return False.
5. Otherwise, enqueue both children (left and right), even if they are null.
6. If you drain the entire queue without finding a gap, return True.

The Python solution

from collections import deque

def isCompleteTree(root):
    queue = deque([root])
    seen_null = False
    while queue:
        node = queue.popleft()
        if node is None:
            seen_null = True
        else:
            if seen_null:
                return False
            queue.append(node.left)
            queue.append(node.right)
    return True

Here is what each part does:

• queue = deque([root]) seeds the queue with the root node.
• seen_null = False tracks whether we have encountered any null in the BFS order so far.
• if node is None: seen_null = True marks that a gap could start here. Every node after this point must also be null.
• if seen_null: return False catches the case where a non-null node appears after a null. That means there is a gap, and the tree is not complete.
• queue.append(node.left) and queue.append(node.right) push both children unconditionally. Null children are pushed too, which is what makes the gap detection work.

Visual walkthrough

Trace BFS through the tree [1, 2, 3, 4, 5, null, 7]. Watch how the seen_null flag flips when we hit the missing left child of node 3, and how node 7 appearing after that null triggers the False return.

The critical moment is step 5. When the queue produces null (the missing left child of node 3), seen_null flips to True. The very next dequeue produces node 7, a non-null value. Since seen_null is already True, we know there is a gap in the level-order sequence, so the tree is not complete.

Complexity analysis

The space is O(n) in the worst case because the bottom level of a complete binary tree holds roughly half of all nodes. The boolean flag seen_null uses O(1) extra space, so the queue dominates.

Building blocks

This problem is built on two reusable patterns:

1. BFS traversal with null children. The standard BFS template skips null children. This variation deliberately enqueues them:

from collections import deque

def bfs_with_nulls(root):
    queue = deque([root])
    while queue:
        node = queue.popleft()
        if node is not None:
            queue.append(node.left)
            queue.append(node.right)

Pushing nulls into the queue lets you reason about the shape of the tree, not just the values. Any problem that needs to detect "missing" nodes in the tree structure can use this variant.

2. Flag-based gap detection. The seen_null flag is a simple state machine with two states: "no gap yet" and "gap found." Once you transition to "gap found," any non-null node is a violation. This pattern applies whenever you need to check that all instances of something come before all instances of something else in a sequence.

Edge cases

• Single node (no children): return True. The root has no children, so BFS enqueues two nulls, seen_null flips, but no non-null node follows. The tree is trivially complete.
• Perfect binary tree (all levels full): return True. Every null appears only after all non-null nodes in the BFS order.
• Last level missing only rightmost nodes: return True. This is the classic definition of a complete tree. The nulls all cluster at the end.
• Node with a right child but no left child: return False. The missing left child creates a null before the right child, which is a gap.

From understanding to recall

You just saw that checking completeness boils down to one boolean flag during BFS. Push nulls into the queue, flip a flag when you see the first null, and reject any non-null that appears after. It is a short solution that makes sense right now. But in an interview next month, will you remember to push null children into the queue instead of skipping them? Will you recall that the flag check goes in the else branch?

Understanding a pattern and being able to reproduce it under pressure are different skills. Spaced repetition bridges that gap. You practice typing the BFS-with-nulls template from memory at increasing intervals. First after a day, then three days, then a week. Each repetition reinforces the null-pushing, the flag flip, and the early return until the pattern is automatic.

BFS with null tracking is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Binary Tree Level Order Traversal - The foundational BFS level-by-level pattern that this problem builds on
• Count Complete Tree Nodes - Another problem that exploits the properties of complete binary trees
• Binary Tree Right Side View - BFS on trees with a different extraction rule per level