Tree BFS (Level-Order Traversal) — Coding Interview Patterns

When a tree (or grid) problem is about levels or shortest distance, you want BFS. The pattern is short, and one small trick — “the queue’s current size is this level” — makes it clean.

The idea

BFS uses a queue (first-in, first-out). Put the root in. To process one whole level:

Note how many nodes are in the queue right now — that count is the current level’s size.
Pop exactly that many, collect their values into this level’s list.
Enqueue each popped node’s children (they form the next level).

Repeat until the queue is empty. The “snapshot the queue size” step is what separates one level from the next, cleanly.

The template

from collections import deque
def level_order(root):
    if not root: return []
    q = deque([root])
    out = []
    while q:
        level = []
        for _ in range(len(q)):       # len(q) = this level's size — the key trick
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level)
    return out
# tree 3 / (9, 20 / (15, 7)) -> [[3], [9,20], [15,7]]

O(n) time (each node once), O(n) space (the queue).

Variations — all small tweaks of the template

Zigzag level order: reverse level on alternate rows (or append to a deque from both ends).
Right-side view: take the last node of each level.
Minimum depth: return the depth of the first level whose node is a leaf (BFS naturally finds the shallowest leaf first — a reason to prefer BFS over DFS here).
Average/largest per level: compute the aggregate of each level list.
Connect level siblings: link nodes within each level as you pop them.

Because BFS reaches nodes in order of distance from the root, it’s also the tool for shortest path in an unweighted graph/grid (Lesson 16) — a grid cell is just a node with up-to-4 neighbours.

Step-by-step walkthrough

Trace Level Order Traversal on the tree 3 → (9, 20), 20 → (15, 7). The trick is to snapshot len(queue) at the start of each round: exactly that many nodes belong to the current level.

level	queue at start	processed this level	queue after (next level)
0	[3]	[3]	[9, 20]
1	[9, 20]	[9, 20]	[15, 7]
2	[15, 7]	[15, 7]	[]

Result: [[3], [9, 20], [15, 7]]. Every node is enqueued and dequeued once — O(n) — and the queue never holds more than one level plus its children.

When to reach for it (BFS vs DFS)

Use BFS when the answer depends on levels or distance: level-order, right-side view, zigzag, minimum depth, shortest unweighted path. Use DFS (Lesson 13) when the answer is about paths, subtree properties, or recursion (max depth, path sum, diameter). If you hear “level”, “shortest”, or “nearest”, think BFS and a queue.

Pitfalls

Reading the level size inside the loop after mutating the queue. Capture len(q) before the inner loop (or in the range), not after you’ve started adding children — otherwise levels bleed together.
Forgetting the empty-tree check. if not root: return [] up front avoids a crash.
Using DFS for a shortest-distance question. DFS doesn’t visit in distance order; for min depth / shortest path, BFS is the right tool.

Recap

Tree BFS processes a tree level by level with a queue, using the “current queue size = this level” trick to separate levels cleanly — O(n). It solves level-order, zigzag, right-side view, min depth and shortest-path-in-a-grid. Reach for BFS when the answer depends on levels or distance; reach for DFS when it’s about paths or subtrees.

Practice: 10 solved problems on tree BFS → — cover each one, solve it yourself, then check the tested code.

Next: Lesson 13 — Tree DFS, the recursive workhorse.