Check Completeness of a Binary Tree — LC 958 BFS Null Sentinel

Problem Statement#

Given the root of a binary tree, determine if it is a complete binary tree. A complete binary tree is one where every level except possibly the last is completely filled, and all nodes in the last level are as far left as possible.

Constraints:

• The number of nodes is in the range [1, 100]
• 1 <= Node.val <= 1000

Input:  root = [1,2,3,4,5,6]
Output: true

Input:  root = [1,2,3,4,5,null,7]
Output: false
        Last level not left-justified (gap before 7).

Why This Problem Matters#

LeetCode 958 Check Completeness of a Binary Tree is a Medium-difficulty interview question asked at Amazon, Meta, Microsoft, and Bloomberg. It is the canonical "BFS with null sentinels" problem and tests whether candidates understand that completeness is a property visible in level-order traversal.

This problem is a great filter: candidates who attempt index-based depth-counting often produce buggy O(n) solutions; those who realize a single BFS sentinel suffices write a clean 12-liner. The technique generalizes to validating heap shapes — a complete binary tree is exactly the shape every binary heap maintains.

In production, similar checks appear when validating serialized heap formats, ensuring tree-based UI layouts have no gaps, and verifying lock-step parallel structures.

The Core Insight#

A binary tree is complete iff, in level-order BFS, no non-null node appears AFTER a null node. Equivalently:

1. Run BFS, enqueueing both real children AND null children (do not skip nulls).
2. Track a flag seenNull = false.
3. Each dequeue: if the node is null, set seenNull = true and continue. If the node is non-null but seenNull is already true, return false.
4. If BFS completes without violation, return true.

This works because completeness is a left-to-right, top-to-bottom contiguity property — exactly what BFS exposes.

Visual Dry Run#

Tree: [1,2,3,4,5,null,7]

        1
       / \
      2   3
     / \   \
    4   5   7

Output: false.

Solution (Optimal)#

from collections import deque
 
class Solution:
    def isCompleteTree(self, root) -> bool:
        if not root:
            return True
        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

var isCompleteTree = function(root) {
    if (!root) return true;
    const queue = [root];
    let seenNull = false;
    while (queue.length) {
        const node = queue.shift();
        if (node === null) {
            seenNull = true;
        } else {
            if (seenNull) return false;
            queue.push(node.left  || null);
            queue.push(node.right || null);
        }
    }
    return true;
};

Time: O(n) — every node and at most n+1 null sentinels visited. Space: O(n) — queue at peak holds one full level.

Common Mistakes#

• Skipping null children in BFS — defeats the entire detection mechanism.
• Returning false at the first null without checking subsequent nodes — single nulls in the last level are legal.
• Trying to use depth counting only — fails on subtle gaps.
• Using queue.shift() in JavaScript on huge inputs — O(n) per shift; for big n, use a head index.
• Treating an empty tree as not complete — by convention an empty tree IS complete; LC 958 starts at n >= 1.

Interview Tips#

• State the invariant: "After the first null, no more non-null nodes are allowed in BFS order."
• Walk through [1,2,3,4,5,null,7] to show the violation.
• Confirm with the interviewer: completeness allows the last level to be partially filled, only left-aligned.
• Note that this is the same shape constraint as a binary heap — a useful framing.

Follow-up Questions#

• Index-based BFS? Assign each node i; complete iff max index == n - 1. Same complexity.
• Recursive solution? Compute heights and validate left-completeness — more code, same O(n).
• Last-level fill ratio? Track null count vs total slots in the last level.
• Repair to complete? Move rightmost nodes to fill leftmost gaps.
• N-ary trees? Generalize to "no non-null after null in BFS"; same proof.

Key Takeaways#

• LeetCode 958 is a Medium-difficulty FAANG tree question asked at Amazon, Meta, and Microsoft.
• The optimal pattern is BFS with null sentinels and a seenNull flag.
• Once a null is dequeued, no subsequent dequeue may produce a non-null node.
• Time complexity O(n); space complexity O(n) for the queue.
• A complete binary tree has exactly the shape of a binary heap.
• Do NOT skip nulls in the queue — they are the detection mechanism.
• The pattern transfers to heap shape validation and serialized tree format checks.