p20 — Hints

Open one at a time.

Hint 1 — BFS, Not DFS

Output is grouped by depth, top to bottom. DFS visits in pre/in/post order, which mixes depths. BFS visits in depth order naturally. Reach for BFS.

Hint 2 — Queue

BFS needs FIFO. In Python: from collections import deque. Use popleft() and append() — both O(1). Never use list.pop(0) — that’s O(N) per call and will tank performance on large inputs.

Hint 3 — The Level Boundary Problem

If you BFS naively, you get all node values in level order but as a flat list. How do you know where one level ends and the next begins?

Answer: snapshot the queue’s size at the start of each level.

while queue:
    n = len(queue)            # ← snapshot
    level = []
    for _ in range(n):        # drain exactly n nodes
        node = queue.popleft()
        level.append(node.val)
        for child in (node.left, node.right):
            if child: queue.append(child)
    out.append(level)

When you start the inner loop, queue contains exactly the current level. By the time the inner loop finishes, you’ve drained that level and the queue now contains the next level. The snapshot n is the boundary marker.

Hint 4 — Why Snapshot Beats Per-Node Depth

You could tag every queued node with its depth: q.append((child, depth + 1)). Then bucket by depth at the end. That works but pays O(N) memory for the depths AND adds a bucketing pass.

The snapshot trick uses the queue’s instantaneous size as an implicit level marker. Cleaner. This is the pattern interviewers want to see.

Hint 5 — DFS Alternative

If you must use DFS (e.g., recursion-only environment):

def dfs(node, depth):
    if not node: return
    if depth == len(result): result.append([])
    result[depth].append(node.val)
    dfs(node.left, depth + 1)
    dfs(node.right, depth + 1)

Same output. O(N) time, O(H) stack. Mention this as the alternative when interviewers ask “can you do it recursively?” — the answer is “with depth tracking, yes; that’s effectively DFS-by-depth, not BFS.”

Be precise: there is no such thing as “recursive BFS.” Recursion uses an implicit LIFO stack; BFS needs a FIFO queue. The recursive version is DFS-with-depth-tracking that happens to produce the same level-grouped output.