Pattern 2: Level-order BFS
Recursion (DFS) goes deep into a branch before coming back. But some questions are about levels — "the values of each level", "the rightmost node of each row", "the minimum depth". For those, breadth-first search (BFS), with a queue, processes the tree layer by layer.
Try it first: Binary Tree Level Order Traversal
Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.
Return the tree's values level by level, top to bottom, left to right — one list per level.
Example: [3,9,20,null,null,15,7] → [[3],[9,20],[15,7]].
Did you try? You can do it with DFS (keeping the depth of each value), but separating the levels gets awkward. The theory below shows the clean way: processing the queue "one level at a time".
The theory: the queue and the level-size trick
BFS uses a queue (FIFO): you enqueue the root and, repeatedly, take the front node and enqueue its children. This visits the nodes in level order (root, then level 1, then level 2...). Watch the queue advance level by level (amber is the node being processed, blue the ones already visited):
But how do you separate the levels into distinct lists? The trick is simple and elegant: at the start of each round, the queue contains exactly one whole level. So capture the current queue size and process only that many nodes — they are the current level; the children you enqueue will form the next:
queue = [root]
while the queue is not empty:
size = len(queue) # ← freeze the current level
level = []
repeat `size` times:
node = dequeue
level.append(node.val)
enqueue node.left and node.right (if they exist)
result.append(level)
Why is it O(n) time and O(n) space?
Each node enters and leaves the queue exactly once → O(n) time. The space is the maximum queue size, which is the width of the tree — in the worst case (the last level of a full tree) it is ~n/2 nodes → O(n) space. Note the contrast with DFS: there the space was O(h) (height); here it is O(width).
DFS or BFS on a tree?
| The question is about... | Use | Why |
|---|---|---|
| a property that combines from the children (height, sum, validate) | recursive DFS | the recursion combines naturally |
| levels (per level, deepest level, side view) | BFS | the queue processes layer by layer |
| minimum depth / "fewest steps" to something | BFS | it finds the shallow level first |
A fun fact that connects to Matrix: this is the same BFS you used in the grid for the shortest path. Trees and grids are graphs; level-by-level BFS is the same algorithm. You are practicing graphs without realizing it.
🧠 Review quiz
0/41. What data structure does BFS use, and in what order does it visit the nodes?
2. How do you separate the levels into distinct lists during BFS?
3. What is the space complexity of BFS on a tree, and why?
4. 'Return the right-side view of the tree (the rightmost node of each level).' Which pattern?
Summary
- BFS uses a queue and visits the tree level by level.
- Separate levels by capturing the queue size at the start of each round.
- O(n) time; O(n) space (width) — contrast with O(h) for DFS.
- Use BFS for per-level questions or ones about minimum depth.
Next lesson: the tree with a golden rule that gives fast search — the BST.