LeetCode 958: Check Completeness of a Binary Tree

Problem Restatement

We are given the root of a binary tree.

We need to determine whether the tree is a complete binary tree.

A complete binary tree has these properties:

1. Every level except possibly the last is completely filled.
2. All nodes in the last level are as far left as possible.

Return true if the tree is complete. Otherwise, return false.

The official problem states this exact definition: every level except possibly the last is completely filled, and all nodes in the last level are as far left as possible.

Input and Output

Example function shape:

def isCompleteTree(root: Optional[TreeNode]) -> bool:
    ...

Examples

Example 1:

root = [1, 2, 3, 4, 5, 6]

Output:

True

The tree is:

        1
      /   \
     2     3
    / \   /
   4   5 6

The last level is filled from left to right. There is no gap before an existing node.

Example 2:

root = [1, 2, 3, 4, 5, None, 7]

Output:

False

The tree is:

        1
      /   \
     2     3
    / \     \
   4   5     7

There is a missing left child under node 3, but a right child 7 exists after that missing position.

That violates completeness.

First Thought: Check Each Level

A complete tree is filled level by level from left to right.

So one idea is to inspect every level and check whether:

1. All levels before the last are full.
2. The last level has no gaps.

This can work, but it requires careful bookkeeping.

There is a simpler way: use level-order traversal and watch for the first missing node.

Key Insight

In a complete binary tree, once we see a missing child position during BFS, every later position must also be missing.

This is the core rule:

after seeing None, we must never see another real node

Why?

BFS visits nodes in level-order from left to right.

A missing position means there is a gap.

If a real node appears after that gap, then the tree has a node farther right while an earlier position is empty. That cannot happen in a complete binary tree.

Algorithm

Use a queue for BFS.

1. Put root into the queue.
2. Keep a boolean flag:

seen_missing = False

3. While the queue is not empty:
   • Pop the next item.
   • If it is None, set seen_missing = True.
   • Otherwise:
     • If seen_missing is already True, return False.
     • Push its left child.
     • Push its right child.
4. If BFS ends without finding a real node after a missing position, return True.

Correctness

BFS visits binary tree positions in the exact order required by completeness: level by level, left to right.

In a complete binary tree, all existing nodes must appear before all missing positions in this traversal. Once a position is missing, every later position must also be missing.

The algorithm records whether it has already seen a missing position.

If it later sees a real node, then a node exists after a gap in level-order order. That means the last level is not filled from left to right, or an earlier level is incomplete. In both cases, the tree is not complete, so returning False is correct.

If the algorithm finishes without seeing any real node after a missing position, then all real nodes appeared before all missing positions in level-order traversal. Therefore, every level before the last is filled, and the last level is filled from left to right. So the tree is complete.

Complexity

Let n be the number of nodes.

Implementation

from collections import deque
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        queue = deque([root])
        seen_missing = False

        while queue:
            node = queue.popleft()

            if node is None:
                seen_missing = True
                continue

            if seen_missing:
                return False

            queue.append(node.left)
            queue.append(node.right)

        return True

Code Explanation

We start BFS from the root:

queue = deque([root])

The flag tracks whether a missing position has appeared:

seen_missing = False

For each item popped from the queue:

node = queue.popleft()

If the item is missing:

if node is None:
    seen_missing = True
    continue

we mark that all later items must also be missing.

If the item is a real node after a missing position:

if seen_missing:
    return False

then the tree has a gap before an existing node, so it is incomplete.

Otherwise, we add both child positions:

queue.append(node.left)
queue.append(node.right)

We add None children deliberately. They represent missing positions in level-order traversal.

If traversal ends cleanly:

return True

the tree is complete.

Testing

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(values):
    if not values:
        return None

    root = TreeNode(values[0])
    queue = deque([root])
    i = 1

    while queue and i < len(values):
        node = queue.popleft()

        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1

        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1

    return root

def run_tests():
    s = Solution()

    root = build_tree([1, 2, 3, 4, 5, 6])
    assert s.isCompleteTree(root) is True

    root = build_tree([1, 2, 3, 4, 5, None, 7])
    assert s.isCompleteTree(root) is False

    root = build_tree([1])
    assert s.isCompleteTree(root) is True

    root = build_tree([1, 2, 3, 4, None, 6, 7])
    assert s.isCompleteTree(root) is False

    root = build_tree([1, 2, 3, 4, 5])
    assert s.isCompleteTree(root) is True

    root = build_tree([1, 2, 3, None, None, 6, 7])
    assert s.isCompleteTree(root) is False

    print("all tests passed")

run_tests()

Test meaning: