Binary Tree Level Order Traversal
BFS a level at a time by draining the queue's current size.
Level Order, a Level at a Time
Problem
Given the root of a binary tree, return its node values grouped by depth from top to bottom. Within each depth, list values from left to right. An empty tree should produce an empty list.
Examples
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Input: root = [1]
Output: [[1]]
The Goal
Return the tree's values level by level: the root's level first, then its children, then theirs, each level left to right. An empty tree gives [].
For [3,9,20,null,null,15,7], that's [[3], [9, 20], [15, 7]].
Breadth-first search already visits nodes in this order. The work is knowing where one level ends and the next begins.
Keep the levels apart
A plain breadth-first search gives 3, 9, 20, 15, 7. The answer needs the same values cut into levels: [3], [9, 20], [15, 7].
BFS order, plus a boundary between levels.
Key Idea: Freeze the Level's Size
When a level starts, the queue holds exactly that level. Save its length as level_size, then pop exactly that many nodes.
Each popped node queues its children, so the queue grows while you drain it. Those children sit behind the level, and the saved count stops the loop before it reaches them. They wait for the next round.
Save level_size = len(queue) before popping anything.
Level 1 starts as [9, 20], so level_size = 2.
The Algorithm
Each pass of the outer loop is one level.
from collections import deque
def level_order(root):
if root is None:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return resultThe for loop runs a fixed level_size times, however much the queue grows inside it.
| Inner loop | What happens | Result |
|---|---|---|
| Saved level_size | Stops at the level's end | [[3], [9, 20], [15, 7]] |
| While the queue isn't empty | Runs on into the children | [[3, 9, 20, 15, 7]] |
Walkthrough
Run it on [3,9,20,null,null,15,7].
The queue starts as [3], so level_size = 1. Popping 3 queues 9 and 20, and level 0 is [3].
Now level_size = 2. Node 9 has no children. Popping 20 queues 15 and 7 behind the level, and the loop stops after its second pop: level 1 is [9, 20].
Level 2 pops 15 and 7, and the queue is empty.
Checkpoint · predict the next step
Step 8 of 22 on the stage: The queue holds all of level 1: level_size = 2. Children queued from here on wait for the next level.
queue = [9, 20] · result = [[3]] · level_size 2 · level []
Pitfalls
- Save the length before the inner loop. A loop on the live queue mixes levels.
- Queue the left child before the right, or each level comes out reversed.
- Skip missing children. Queuing
Noneputs holes in the levels. - An empty tree returns
[], not[[]]. - A single node returns
[[value]].
The queue is [9, 20] when level 1 starts. How many pops finish the level?
Complexity
Each node is queued once, popped once, and checks two children, so time is O(n). The nested loop doesn't make it quadratic: across all its passes, it pops each node once.
The queue holds at most about one level, up to n / 2 nodes in a full tree, and the answer holds all n values. Space is O(n).
Breadth-first, a level at a time
- Queue and pop each nodeOnce each.dominantO(n)
- Check childrenTwo per node.dominantO(n)
- Queue and resultThe widest level, and every value.dominantO(n)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
Every node has to be read, so linear time is as fast as it gets.
In short
Use a queue seeded with the root. At each level, record the current queue size, then dequeue exactly that many nodes (collecting their values and enqueueing their children). Each batch is one level's output.
Common mistake
Not snapshotting the queue length before the inner loop, which mixes nodes from two levels together.