PATTERN 10 OF 22

Trees (BFS)

Traverse binary trees level by level using a queue. Master the queue-plus-level-size pattern to solve problems that require processing nodes one level at a time, including level-order traversal, per-level aggregation, and BFS-based serialization.

Time: O(n)

Space: O(w) where w = max tree width

Learn & Reference

Understanding the Pattern

Trees (BFS) Pattern

Breadth-first search (BFS) explores a binary tree level by level, visiting all nodes at depth 0, then all at depth 1, then depth 2, and so on. While DFS dives deep along one branch before backtracking, BFS sweeps horizontally across the tree. The core data structure is a queue — nodes enter at the back and leave from the front, naturally producing level-order output.

Core Concept

BFS starts by enqueueing the root. On each iteration, it dequeues a node, processes it, and enqueues that node's children. Because children are always added after their parent's level, the queue always contains nodes in level order.

        1            Level 0: [1]
       / \
      2   3          Level 1: [2, 3]
     / \   \
    4   5   6        Level 2: [4, 5, 6]

BFS visit order: 1, 2, 3, 4, 5, 6

The key challenge in interviews is not just visiting nodes in order — it is knowing which nodes belong to the same level. This is where the level-size trick comes in.

Key Techniques

1. The Level-Size Trick

This is THE BFS interview pattern. At the start of each level, snapshot the current queue length. That number tells you exactly how many nodes belong to the current level. Process that many nodes, enqueueing their children, and you have cleanly separated one level from the next.

while queue is not empty:
    level_size = len(queue)        # snapshot!
    for i in range(level_size):
        node = queue.popleft()
        process(node)
        if node.left:  queue.append(node.left)
        if node.right: queue.append(node.right)

Without the snapshot, newly enqueued children mix with the current level's nodes, and you lose track of level boundaries.

2. Per-Level Aggregation

Once you can isolate each level, you can extract information per level:

Collect all values: level-order traversal — append each level's values as a subarray
Last element only: right-side view — the last node processed at each level is the rightmost
First element only: left-side view — the first node at each level
Max / min / average: compute aggregates over the level's nodes

The template is always the same: level-size snapshot, inner loop, extract what you need.

3. Direction Alternation (Zigzag)

Some problems require alternating the direction each level is read. Level 0 left-to-right, level 1 right-to-left, level 2 left-to-right, and so on.

The simplest approach: collect each level normally (left-to-right via BFS), then reverse the level array when the direction flag says right-to-left. Toggle the flag after each level.

4. BFS-Based Serialization

BFS can serialize a tree by recording node values level by level, using a sentinel (like "N") for null children. Deserialization reads tokens in the same level-order: create the root from the first token, then for each parent node in a queue, read two tokens for its left and right children.

This is an alternative to DFS preorder serialization. BFS serialization produces a format that matches the intuitive "array representation" of a tree.

5. BFS vs DFS — When to Choose BFS

Use BFS when:

You need level-by-level processing (e.g., level-order traversal, averages per level)
You need the shallowest occurrence (shortest path in an unweighted tree)
You need per-level metadata (level number, width, rightmost/leftmost node)

Use DFS when:

The problem is naturally recursive (max depth, validate BST, path sum)
You need root-to-leaf paths
Space matters and the tree is balanced (DFS uses O(h) vs BFS O(w))
The tree is narrow and deep — DFS stays within O(h) while BFS may hold many nodes

When BFS Fails

Deep recursive properties: computing subtree sums, validating BST constraints, or finding lowest common ancestor are far more natural with DFS
Very wide trees: a complete binary tree at depth d has 2^d nodes in the last level — BFS holds all of them in the queue at once
Path-from-root problems: DFS naturally tracks the path via the call stack; BFS would need an auxiliary parent map

Common Mistakes

Forgetting to snapshot queue length: Without level_size = len(queue) at the start of each level, you process children from the next level within the current level's loop, corrupting your level boundaries. Always capture the queue length before the inner loop
Modifying the queue while iterating: In languages where for node in queue iterates over a live collection, appending children during iteration causes infinite loops or skipped nodes. Always use an index-based loop with the snapshot length
Not handling the empty tree: When root is null, you must return early before initializing the queue. Enqueueing null and then trying to access .val causes a null pointer error
Using BFS when DFS is simpler: For problems like max depth or validate BST, BFS works but requires more code than a 3-line recursive DFS. Choose the simpler tool for the problem
Forgetting to initialize level metadata: Many BFS problems need a flag (zigzag direction), a counter (level number), or an accumulator (level sum). Failing to reset or toggle these between levels leads to subtle bugs

When to Use

Level order traversal or level by level in the problem statement

Return nodes at each level or group by level

Right-side view, left-side view, or any per-level query

Zigzag or spiral-order traversal

Minimum depth or shortest path in a tree (BFS finds this naturally)

Average, maximum, or minimum at each level

Connecting nodes at the same level (next pointers)

BFS-based serialization / deserialization

Keywords: level order, breadth-first, queue, BFS, level, width, layer, zigzag, spiral

Template

1# --- TreeNode Definition ---
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8# --- BFS Level-Order Template ---
9from collections import deque
10
11def bfs(root):
12    if not root:
13        return []
14    result = []
15    queue = deque([root])
16    while queue:
17        level_size = len(queue)       # snapshot current level
18        level = []
19        for _ in range(level_size):
20            node = queue.popleft()
21            level.append(node.val)    # process node
22            if node.left:
23                queue.append(node.left)
24            if node.right:
25                queue.append(node.right)
26        result.append(level)          # finished one level
27    return result

{ }

Syntax Reference

1# --- Python: Queue for BFS ---
2from collections import deque
3
4# Create a queue and seed with root
5queue = deque([root])
6
7# Dequeue from front
8node = queue.popleft()     # O(1)
9
10# Enqueue to back
11queue.append(child)        # O(1)
12
13# Check if empty
14if not queue:
15    # queue is empty
16
17# Queue length (for level-size trick)
18level_size = len(queue)
19
20# --- TreeNode Definition ---
21class TreeNode:
22    def __init__(self, val=0, left=None, right=None):
23        self.val = val
24        self.left = left
25        self.right = right

📋

Common Recipes

1# --- Level-Order Traversal (with level grouping) ---
2from collections import deque
3
4def level_order(root):
5    if not root:
6        return []
7    result = []
8    queue = deque([root])
9    while queue:
10        level_size = len(queue)
11        level = []
12        for _ in range(level_size):
13            node = queue.popleft()
14            level.append(node.val)
15            if node.left:
16                queue.append(node.left)
17            if node.right:
18                queue.append(node.right)
19        result.append(level)
20    return result
21
22# --- Right Side View (BFS) ---
23def right_side_view(root):
24    if not root:
25        return []
26    result = []
27    queue = deque([root])
28    while queue:
29        level_size = len(queue)
30        for i in range(level_size):
31            node = queue.popleft()
32            if i == level_size - 1:
33                result.append(node.val)
34            if node.left:
35                queue.append(node.left)
36            if node.right:
37                queue.append(node.right)
38    return result
39
40# --- Zigzag Level Order ---
41def zigzag_level_order(root):
42    if not root:
43        return []
44    result = []
45    queue = deque([root])
46    left_to_right = True
47    while queue:
48        level_size = len(queue)
49        level = deque()
50        for _ in range(level_size):
51            node = queue.popleft()
52            if left_to_right:
53                level.append(node.val)
54            else:
55                level.appendleft(node.val)
56            if node.left:
57                queue.append(node.left)
58            if node.right:
59                queue.append(node.right)
60        result.append(list(level))
61        left_to_right = not left_to_right
62    return result

O(n)

Complexity

Operation	Time	Space
BFS traversal (all nodes)	O(n)	O(w)
Level-order with grouping	O(n)	O(w)
Right/left side view	O(n)	O(w)
Zigzag level order	O(n)	O(w)
BFS serialize/deserialize	O(n)	O(n)
Balanced tree: w ≈ n/2	-	O(n)
Skewed tree: w = 1	-	O(1)

Watch Out

✗**Deep recursive properties**: computing subtree sums, validating BST constraints, or finding lowest common ancestor are far more natural with DFS
✗**Very wide trees**: a complete binary tree at depth d has 2^d nodes in the last level — BFS holds all of them in the queue at once
✗**Path-from-root problems**: DFS naturally tracks the path via the call stack; BFS would need an auxiliary parent map
✗Forgetting to snapshot queue length: Without `level_size = len(queue)` at the start of each level, you process children from the next level within the current level's loop, corrupting your level boundaries. Always capture the queue length before the inner loop
✗Modifying the queue while iterating: In languages where `for node in queue` iterates over a live collection, appending children during iteration causes infinite loops or skipped nodes. Always use an index-based loop with the snapshot length
✗Not handling the empty tree: When root is null, you must return early before initializing the queue. Enqueueing null and then trying to access `.val` causes a null pointer error
✗Using BFS when DFS is simpler: For problems like max depth or validate BST, BFS works but requires more code than a 3-line recursive DFS. Choose the simpler tool for the problem
✗Forgetting to initialize level metadata: Many BFS problems need a flag (zigzag direction), a counter (level number), or an accumulator (level sum). Failing to reset or toggle these between levels leads to subtle bugs

PRACTICE PROBLEMS

Trees (DFS)

Heaps / Priority Queues