patternDSA/Tree BFS
Core Pattern → Pattern 15

Tree Breadth First Search

One queue. One template. Snapshot the level size before processing. Every tree level-order problem is a variation on the same 6-line skeleton.

Frequency:★★★★★
·~25 min·Beginner–Intermediate·9 problems
The Core Shock

DFS with depth tracking for level problems — awkward. BFS with a queue — natural

DFS + depth param
O(n) but messy
Recursive, out-of-order, harder to extend for level ops
BFS + queue
O(n) · clean
Level-by-level, one template covers all variations

The insight: a queue processes nodes in exactly the order they should appear — level by level, left to right. Snapshot level_size = len(queue) before processing each level — that's the boundary between levels. One template, nine problems.

The Universal Template

Memorize these 6 lines. Every Tree BFS problem starts here.

bfs_template.pyO(n) time · O(n) space
1from collections import deque
2 
3def bfs_template(root):
4    if not root: return []
5    queue = deque([root])
6    result = []
7 
8    while queue:                          # while nodes remain
9        level_size = len(queue)           # <- SNAPSHOT: current level boundary
10        current_level = []
11 
12        for _ in range(level_size):       # process exactly this level
13            node = queue.popleft()
14            current_level.append(node.val)
15            if node.left:  queue.append(node.left)
16            if node.right: queue.append(node.right)
17 
18        result.append(current_level)      # save completed level
19 
20    return result
The level_size snapshot is the entire trick. After you call level_size = len(queue), the inner for-loop processes exactly those nodes — children are added to the queue but aren't counted. Without this snapshot, you lose level boundaries entirely.

All Variations From One Template

One template, six variations — each adds exactly one line to the skeleton.

Level Order
Append current_level to result
Reverse Level Order
result.insert(0, level) OR reverse at end
Zigzag Traversal
deque + left_to_right flag + appendleft
Level Averages
sum(level) / len(level) per level
Minimum Depth
Return level when first leaf found (no children)
Right View
Take last node of each level: current_level[-1]
Connect Level Siblings
prev.next = node; track prev per level
Connect All Siblings
prev.next = node; no level boundary check

Pattern Recognition

BFS vs DFS — know which to reach for.

Use Tree BFS When
"Level order", "level by level", "level averages"
"Minimum depth" or "closest" leaf/node
"Right view" or "left view" of tree
"Connect nodes at same level"
"Zigzag" or "spiral" traversal
"Level order successor" of a node
"Shortest path" in unweighted tree/graph
Any problem needing level-boundary awareness
Common Pitfalls
Using queue.pop() (LIFO) instead of popleft() (FIFO)
Not snapshotting level_size — loses level boundaries
Using list.pop(0) instead of deque — O(n) per pop
Min depth: returning on first node with one null child (must be leaf)
Right view: recording first node not last per level
Connect siblings: not handling level boundaries (prev from prev level)
Forgetting 'if not root: return []' null check
Zigzag: using list.insert(0) instead of deque.appendleft