Binary Tree Level Order Traversal — The Yearbook Rows

Boss 8: The Yearbook Rows

Seven bosses of depth: dive down a branch, come back, dive again. This boss turns the whole dungeon sideways and sweeps the tree one level at a time. Breadth-first search, powered by the humble queue, and it's the tool behind roughly a third of all tree interview questions ("by level", "zigzag", "rightmost per level", "average per level"... one engine, many hats).

The story

The school's centennial mural paints the founding family as a tree:

        Founder (3)
        /        \
   Daughter(9)  Son(20)
                /     \
          Grandkid(15) Grandkid(7)

The yearbook's photo spec is rigid: shoot it row by row. Row 1: the founder. Row 2: daughter, then son. Row 3: the two grandkids, left to right. The final layout:

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

Try to shoot this with the dungeon's usual deep-dive style and feel the mismatch: a depth-first walk visits Founder → Daughter → back up → Son → Grandkid 15 → ..., bouncing between generations. You'd need to label each shot with its row and sort it all afterward. (Genuinely workable! Hold that thought.)

The photographer's actual technique is a waiting line:

1. The line starts holding just the founder.
2. Photograph the person at the front of the line. As you do, their children join the back of the line.
3. Repeat until the line is empty.

Founder is shot, daughter and son join. Daughter is shot (her kids: none), son is shot, his two kids join. Then the grandkids, in the order they joined, which is left to right. The queue preserves generation order automatically: everyone from generation k stands in line ahead of everyone from generation k+1, because parents joined before their children could.

The problem, dressed up properly

Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level).

LeetCode 102. Note the output shape: not a flat list, a list of lists, one inner list per level. That inner grouping is where the boss hides its one real trick.

The naive attempt

The hold-that-thought version: depth-first walk carrying a depth label, appending each value into its row's bucket.

def level_order(root):
    rows = []
    def walk(node, depth):
        if not node:
            return
        if depth == len(rows):
            rows.append([])
        rows[depth].append(node.val)
        walk(node.left, depth + 1)
        walk(node.right, depth + 1)
    walk(root, 0)
    return rows

Here's the twist for a "naive attempt" section: this is correct, O(n), and interview-acceptable. DFS visits left before right, so within each bucket, order comes out left-to-right. Its real cost is conceptual: it answers a breadth-shaped question with depth-shaped machinery, and it keeps O(h) stack plus the row structure. The BFS version answers it natively, and BFS is the skill this boss exists to install, because the follow-up questions (zigzag, right-side view, "kill the tree floor by floor") stop yielding to relabeled DFS so gracefully.

The weapon: a queue, and the snapshot count

The photographer's line is a FIFO queue: push to the back, pop from the front. The plain loop gives a flat generation-ordered stream. The one missing piece is where one row ends, and the trick is disarmingly small:

At the moment a row begins, the queue contains exactly that row and nothing else. Everyone from the previous row has been shot and left; their children (the next row) haven't been processed yet. So: snapshot len(queue), pop exactly that many, and that's one complete row, while their children quietly accumulate behind them for the next round.

Watching it work

queue: [3]                 snapshot 1
  pop 3 → row [3], push 9, 20
queue: [9, 20]             snapshot 2
  pop 9  → row [9],  no children
  pop 20 → row [9, 20], push 15, 7
queue: [15, 7]             snapshot 2
  pop 15 → row [15]
  pop 7  → row [15, 7]
queue: []                  done

output: [[3], [9, 20], [15, 7]] ✓

Note the third snapshot is 2, not 3: the snapshot counts people in line, not the row number. Misread that once here and you'll never misread it in code.

The code

from collections import deque
 
def level_order(root: TreeNode | None) -> list[list[int]]:
    if not root:
        return []
    rows = []
    queue = deque([root])
    while queue:
        row = []
        for _ in range(len(queue)):      # snapshot: this generation only
            node = queue.popleft()
            row.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        rows.append(row)
    return rows

range(len(queue)) is evaluated once, at the top of the row, that's the snapshot. The children appended mid-row swell the queue, but the loop bound was already locked in.

Gotchas

1. Popping from the wrong end. queue.pop() (the right end) turns your queue into a stack and BFS into DFS, and the rows interleave into nonsense. popleft(), and use a real deque: list.pop(0) is O(n) per pop, silently turning the traversal quadratic.

2. No snapshot. while queue: with a single unbounded inner drain gives one flat list, generations merged. Fine for "traverse", wrong for "traverse by level". The for _ in range(len(queue)) is the entire difference.

3. Pushing None children. Appending node.left unguarded means popping Nones later, then either crashing or writing None-checks at the pop. Filter at the push, the queue stays clean.

4. Recomputing len(queue) in the loop condition. while i < len(queue) re-reads the growing queue and the row boundary dissolves. The snapshot must be taken once and stored (or locked into range).

Complexity

Every node enters and leaves the queue exactly once.

Time: O(n). Space: O(w) where w is the tree's maximum width, up to n/2 for a bushy tree's bottom row. Note the trade against DFS: recursion pays for height, BFS pays for width. Deep skinny tree → BFS is cheap. Wide bushy tree → DFS is cheap. Neither dominates; the tree's shape picks.

Boss down. XP gained.

The mural spread runs three tidy rows in the centennial yearbook, every face in its generation, and the photographer never once climbed the scaffolding out of order.

What you walked away with:

• BFS: pop the front, push the children, and the queue sorts the generations for free
• The snapshot trick: len(queue) at row start = exactly one level, children accumulate behind
• DFS-with-depth-labels also solves it, but the queue is the native tool, and the variants demand it
• Stack space scales with height, queue space with width, know which your tree punishes

Next up: Boss 9 — The Skyline Sketch. An artist sits in a hot-air balloon due east of a tree-shaped apartment tower and sketches what she sees: exactly one apartment per floor, the rightmost one, everything behind it hidden. One line changes in today's engine, and there's a sneaky DFS alternative that visits right children first and trusts the depth to say who's visible.