Binary Tree Level Order Traversal — Solution

Problem

Given the root of a binary tree, return the values of its nodes grouped by depth level, from the root down to the leaves. Each depth gets its own inner list in the output.

Example:

[3,9,20,null,null,15,7]

• Input: root = [3, 9, 20, null, null, 15, 7]
• Output: [[3], [9, 20], [15, 7]]
• Explanation: Level 0 holds just the root (3), level 1 holds its two children (9, 20), and level 2 holds their children (15, 7).

Intuition

The problem is a breadth-first traversal: finish all nodes at depth 0 before moving to depth 1, then depth 2, and so on. A queue enforces this ordering naturally — when you dequeue a node, you enqueue its children, guaranteeing each generation is fully processed before the next one begins. The key insight is snapshotting the queue's size at the start of each iteration; that count tells you exactly how many nodes belong to the current level before any new children are added.

Solution — BFS with Level Snapshot

Initialize a queue with the root and process it level by level. At each step, capture the current queue length before enqueueing any children — that snapshot count bounds the inner loop to exactly the nodes at the current depth.

Steps:

1. Return an empty list immediately if root is null.
2. Initialize a queue containing only the root.
3. While the queue is non-empty, record level_size = len(queue).
4. Dequeue exactly level_size nodes, appending each value to a temporary list.
5. For each dequeued node, enqueue its non-null left and right children.
6. Append the temporary list as one completed level in the result.
7. Return result once the queue is empty.

1from collections import deque
2
3def levelOrder(root):
4    if not root:
5        return []
6    result = []
7    queue = deque([root])
8    while queue:
9        level_size = len(queue)  # snapshot before any children are enqueued this round
10        level_values = []
11        for _ in range(level_size):
12            node = queue.popleft()
13            level_values.append(node.val)
14            if node.left:
15                queue.append(node.left)
16            if node.right:
17                queue.append(node.right)
18        result.append(level_values)
19    return result

• Time: O(n) — every node is enqueued and dequeued exactly once.
• Space: O(n) — the queue holds at most the widest level; a complete binary tree's bottom row contains roughly n/2 nodes.

Complexity Summary

Common Mistakes

• Not snapshotting the queue size before the inner loop — using while queue as the inner loop condition drains the entire queue in a single pass, collapsing all levels into one flat list. Always capture level_size = len(queue) before enqueueing any children.
• Enqueueing null children — failing to check if node.left before appending causes a null pointer crash when the next iteration dequeues that null and tries to read .val; guard both children explicitly.
• Returning [[]] instead of [] for an empty tree — skipping the null check on root causes the outer while loop to run once on an empty queue, appending an empty level to the result. Return [] immediately when root is null.
• Using a null sentinel to separate levels — enqueueing null after each level's nodes is a valid alternative, but it silently breaks if root itself is null and requires extra handling at initialization. The snapshot approach is simpler and avoids sentinel logic entirely.

Related Problems

• binary-tree-zigzag-level-order-traversal — same BFS skeleton but alternates the direction each level is appended
• binary-tree-right-side-view — level-order traversal where you only keep each level's last node
• rotting-oranges — multi-source BFS on a grid using the same level-snapshot pattern
• maximum-level-sum-of-a-binary-tree — level-order traversal with per-level aggregation to find the maximum sum
• minimum-depth-of-binary-tree — BFS naturally stops at the first level containing a leaf, making it more efficient than DFS here