Introduction

A binary tree is complete if every level is full except possibly the last, and the last level is filled from left to right with no gaps. The easiest way to check that property is to traverse the tree in level order and verify that once a missing child position appears, no later real node appears after it.

The Core Property

A complete binary tree allows missing nodes only at the far right end of the last level. That gives us a useful test:

• scan the tree level by level from left to right
• once you encounter a None position, every later position must also be None

If a real node appears after a gap, the tree is not complete.

Breadth-First Search Solution

This rule maps directly to a queue-based breadth-first traversal.

1from collections import deque
2
3class Node:
4    def __init__(self, value, left=None, right=None):
5        self.value = value
6        self.left = left
7        self.right = right
8
9
10def is_complete(root):
11    if root is None:
12        return True
13
14    queue = deque([root])
15    seen_gap = False
16
17    while queue:
18        node = queue.popleft()
19
20        if node is None:
21            seen_gap = True
22            continue
23
24        if seen_gap:
25            return False
26
27        queue.append(node.left)
28        queue.append(node.right)
29
30    return True
31
32
33root = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), None))
34print(is_complete(root))

This prints True for a complete tree.

Why The Algorithm Works

Level-order traversal visits nodes in the exact order that completeness is defined. If the tree is complete, all actual nodes occupy the leftmost available positions, so after the first empty slot there can be no later real node.

If a later real node does appear, the tree has a gap before a node on the same level or a lower level, which violates completeness.

Example Of An Incomplete Tree

Consider this structure:

• root has both children
• the left child is missing a left node but has a right node

That already breaks completeness because a node appears to the right of a gap.

bad = Node(1, Node(2, None, Node(5)), Node(3))
print(is_complete(bad))

This prints False.

Index-Based Alternative

Another common method numbers nodes as if the tree were stored in an array. In such a layout:

• root gets index 0
• left child gets 2 * i + 1
• right child gets 2 * i + 2

If the tree has n real nodes and is complete, the largest assigned index must be less than n.

1def count_nodes(root):
2    if root is None:
3        return 0
4    return 1 + count_nodes(root.left) + count_nodes(root.right)
5
6
7def is_complete_indexed(root, index, total_nodes):
8    if root is None:
9        return True
10    if index >= total_nodes:
11        return False
12    return (
13        is_complete_indexed(root.left, 2 * index + 1, total_nodes)
14        and is_complete_indexed(root.right, 2 * index + 2, total_nodes)
15    )
16
17
18def check_complete(root):
19    total = count_nodes(root)
20    return is_complete_indexed(root, 0, total)

This method is also correct, but it requires either two passes or a combined recursive structure. The queue method is often easier to explain in interviews.

Complexity

Both common approaches run in O(n) time because each node is visited a constant number of times. The queue-based approach uses O(n) space in the worst case for the traversal queue. The indexed recursive approach uses O(h) call stack space, where h is the tree height, plus any space used to count nodes.

Common Pitfalls

The most common mistake is checking only whether every node has either zero or two children. That tests for a full tree, not a complete tree, and it rejects many valid complete trees.

Another mistake is traversing depth-first and trying to infer left-to-right level constraints from local shape alone. Completeness is fundamentally a level-order property, so BFS is the safer direct method.

A third issue is mishandling the empty tree. By convention, an empty tree is complete.

Summary

• A complete binary tree can have missing nodes only at the far right of the last level.
• A level-order traversal with a gap flag gives a clean O(n) solution.
• Once a None position is seen, no later real node may appear.
• The indexed-array method is a valid alternative with the same asymptotic time complexity.
• Do not confuse complete trees with full or perfect trees.