Pattern 08: BFS (Breadth-First Search)

0. The Template (Copy-Paste Skeleton)

One skeleton, three surfaces: tree, grid, generic graph. The line that makes it work is int size = queue.size(); — freeze it, or your levels bleed into each other.

// TEMPLATE A — LEVEL-ORDER BFS ON A TREE
List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> out = new ArrayList<>();
    if (root == null) return out;                 // ALWAYS null-check the root first

    Queue<TreeNode> q = new ArrayDeque<>();
    q.offer(root);

    while (!q.isEmpty()) {
        int size = q.size();                      // ← FREEZE: exactly one level
        List<Integer> level = new ArrayList<>(size);

        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            level.add(node.val);
            if (node.left  != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        out.add(level);
    }
    return out;
}

// TEMPLATE B — BFS ON A GRID (shortest path in an unweighted grid)
static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};   // add diagonals for 8-directional

int bfs(int[][] grid, int sr, int sc) {
    int rows = grid.length, cols = grid[0].length;
    Queue<int[]> q = new ArrayDeque<>();
    boolean[][] seen = new boolean[rows][cols];

    q.offer(new int[]{sr, sc});  seen[sr][sc] = true;       // mark ON ENQUEUE
    int steps = 0;

    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            int[] cur = q.poll();
            if (isTarget(cur)) return steps;
            for (int[] d : DIRS) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                if (seen[nr][nc] || grid[nr][nc] == BLOCKED) continue;
                seen[nr][nc] = true;
                q.offer(new int[]{nr, nc});
            }
        }
        steps++;
    }
    return -1;                                              // unreachable
}

// TEMPLATE C — MULTI-SOURCE BFS (everything spreads at once) — seed ALL sources at level 0
for (each source s) { q.offer(s); seen[s] = true; }
// ...then the identical loop as Template B. That's the whole change.

The four rules

1. int size = q.size() before the inner loop — this is what makes BFS level-aware. Without it you cannot answer “how many steps / levels / minutes”.
2. Mark visited when you ENQUEUE, not when you dequeue. Otherwise the same node is enqueued by every neighbour, the queue grows to O(E), and counters get double-incremented.
3. ArrayDeque, not LinkedList. Array-backed, no node allocation, cache-friendly.
4. BFS gives the shortest path only when every edge costs the same. Weighted edges → Dijkstra. Weights of only 0 and 1 → 0-1 BFS with a deque (offerFirst for 0, offerLast for 1).

BFS vs DFS

Need	Use
shortest / minimum steps, level info	BFS
all paths, path state, backtracking, connectivity only	DFS
very deep graph (stack-overflow risk)	BFS, or iterative DFS
very wide graph (memory blowup at one level)	DFS

---

1. Pattern Identification & Logic

How to Identify (Interview Triggers)

• “Level order” traversal or “layer-by-layer”
• “Shortest path” in an unweighted graph
• “Right side view” / “Left side view” of a tree
• “Average of each level”
• “Connect siblings at same level”

The Algorithm (Pseudocode)

queue = new Queue()
queue.add(root)

while queue is not empty:
    levelSize = queue.size()       // FREEZE the level count

    for i = 0 to levelSize - 1:
        node = queue.poll()
        process(node)

        if node.left:  queue.add(node.left)
        if node.right: queue.add(node.right)

The ‘Trick’ to Know

• Always capture queue.size() BEFORE the inner loop starts. This “freezes” the level boundary so you don’t accidentally process next-level nodes in the current iteration.
• BFS guarantees shortest path in unweighted graphs because it explores all distance-1 nodes before distance-2 nodes.

---

2. Java Implementation (Brute Force vs. Optimal)

Example Problem: Binary Tree Level Order Traversal - LC 102

Brute Force: DFS with Level Tracking - O(n)

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    private void dfs(TreeNode node, int level, List<List<Integer>> result) {
        if (node == null) return;

        if (level == result.size()) {
            result.add(new ArrayList<>());
        }

        result.get(level).add(node.val);
        dfs(node.left, level + 1, result);
        dfs(node.right, level + 1, result);
    }
}

Optimal: BFS with Queue - O(n)

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);

                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }

            result.add(currentLevel);
        }

        return result;
    }
}

Java Architecture Insights

• LinkedList as Queue: Queue<TreeNode> q = new LinkedList<>() is standard. ArrayDeque is faster but doesn’t allow null elements (not an issue for tree nodes that exist).
• queue.add() vs queue.offer(): Both work for unbounded queues. offer() returns false instead of throwing exception on bounded queues. In interviews, either is fine.
• Why BFS over DFS here? DFS works functionally but doesn’t demonstrate understanding of level-by-level processing. Interviewers specifically want to see Queue-based BFS.

---

3. Mental Model & Visualization

ASCII Diagram (Level Order of sample tree)

Tree:     3
         / \
        9   20
           / \
          15   7

Queue state over time:

Level 0: | 3 |           → process 3, add 9,20
Level 1: | 9 | 20 |      → process 9,20, add 15,7
Level 2: | 15 | 7 |      → process 15,7, no children

Result: [[3], [9, 20], [15, 7]]

Senior Mental Trigger

“Level-by-level or shortest path = BFS with a Queue, always freeze level size.”

---

4. Curated Problem Lists

Commonly Asked (Bread & Butter)

#	Problem	Difficulty
LC 102	Binary Tree Level Order Traversal	Medium
LC 107	Level Order Traversal II (Bottom Up)	Medium
LC 199	Binary Tree Right Side View	Medium
LC 637	Average of Levels in Binary Tree	Easy
LC 111	Minimum Depth of Binary Tree	Easy

FAANG ‘Aha!’ Level (Hard/Unintuitive)

#	Problem	Difficulty
LC 103	Zigzag Level Order Traversal	Medium
LC 127	Word Ladder	Hard
LC 994	Rotting Oranges	Medium
LC 542	01 Matrix	Medium
LC 117	Populating Next Right Pointers II	Medium

---

5. Time & Space Complexity Table

Approach	Time	Space	Notes
DFS	O(n)	O(h)	h = height of tree (recursion stack)
BFS	O(n)	O(w)	w = max width (last level has ~n/2 nodes)