Coding Interview PatternsCheck Completeness of a Binary Tree
MediumTree Breadth-First Search

Check Completeness of a Binary Tree

Explanation & Solution

Practice Problem

Description

Given the root of a binary tree, determine if it is a complete binary tree.

In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. The last level can have between 1 and 2ʰ nodes inclusive, where h is the height of the tree.

Examples

Example 1:

```tree

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

`

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

Output: true

Explanation: Every level before the last is full, and all nodes in the last level are as far left as possible.

Example 2:

```tree

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

`

Input:root = [1, 2, 3, 4, 5, null, 7]
0
1
1
2
2
3
3
4
4
5
5
null
6
7

Output: false

Explanation: Node 7 is on the right side of level 2, but the position to its left (node 3's left child) is empty. This violates the completeness property.

Example 3:

```tree

[1]

`

Input:root = [1]
0
1

Output: true

Constraints

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

Approach

Tree Breadth-First Search pattern

1. Handle Empty Tree

  • If root is null, return true (an empty tree is trivially complete)

2. Initialize BFS

  • Create a queue initialized with the root node
  • Track a boolean seenNull — whether we've encountered a null node yet

3. BFS with Null Detection

  • Process nodes from the queue one at a time:
  • If the current node is null:
  • Set seenNull = true
  • If the current node is not null:
  • If seenNull is already true, return false — a non-null node after a gap means the tree is not complete
  • Otherwise, push both node.left and node.right into the queue (even if they are null)

4. Return True

  • If BFS completes without finding a non-null node after a null, the tree is complete

Key Insight

  • In a complete binary tree, when we do BFS (level order), all null nodes must come after all non-null nodes
  • The moment we see a null, every subsequent node must also be null
  • If we ever see a non-null node after a null, the tree is not complete
Time
O(n)every node is visited once
Space
O(n)the queue holds at most one level of nodes

Visualization

Input:
DFS Traversal[1, 2, 3, 4, 5, 6]
123456
output0

Press play to start DFS traversal

CurrentIn stackComplete
13 steps

Solution Code

Previous
Find Largest Value in Each Tree Row
Next
Add One Row to Tree