Tree BFS
Level-order traversal using a queue; emit one level at a time.
Level-by-level processing, shortest path in unweighted graph, right side view, zig-zag.
Every node is enqueued and dequeued exactly once. The queue can hold an entire level at once, which is up to n/2 nodes in a perfect binary tree.
Level-order traversal uses a queue. The trick to emitting one level at a time is to snapshot the queue size at the start of each iteration: that count is exactly the number of nodes at the current level, and you process them in a bounded inner loop before the next level's nodes affect the outer loop.
BFS on trees is the natural fit whenever the answer depends on depth: shortest path (counted in edges), level-by-level aggregates (averages, sums, rightmost view), or zig-zag where alternating levels reverse direction. It's also the right tool for 'minimum depth' problems where DFS would explore deep branches unnecessarily.
Space is O(W) where W is the maximum level width — for a balanced binary tree that's O(n/2) = O(n) at the leaves. This is worse than DFS's O(h) stack on balanced trees but better on pathological skewed trees. The traversal time is always O(n).
Snapshotting queue.size() at the start of each outer-loop iteration cleanly partitions nodes by level — the inner loop processes exactly one level even as it enqueues the next.
- Reading queue.size() inside the inner loop's condition, which sees the next level's enqueued nodes and breaks the level boundary.
- Forgetting to null-check children before enqueueing, double-counting depth or NPE'ing on leaves.
- Using a stack instead of a queue and getting DFS order silently.
- For zig-zag, reversing the level list after building it (correct but slow); using a deque and alternating push-front/push-back is cleaner.
- For shortest path in unweighted graphs, marking visited at dequeue instead of enqueue, allowing the same node to be queued multiple times.
- Level order with per-level lists: snapshot size, inner loop, append to current level list.
- Right side view: take the last node processed in each level's inner loop.
- Zig-zag: alternate append direction per level, or use a deque.
- Minimum depth: return early on the first leaf encountered.
// import java.util.*;
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
return result;Problems using this pattern
3Easiest first · Blind 75 above NeetCode 150