BFS LeetCode Pattern Guide — Shortest-Path, Level-Order, and Multi-Source

A BFS LeetCode pattern guide is a guide to exploring by distance. Shortest-path, level-order, and multi-source problems all rely on the same property: breadth-first search visits nodes in increasing number of steps when every edge has equal weight. If you can recognize that property, many tree, graph, grid, and word-transformation problems become queue-management exercises instead of guesswork.

BFS LeetCode pattern guide: when the queue is the clue

Use BFS when the problem asks for nearest, minimum steps, fewest moves, level by level, spreading over time, or all nodes at distance k. DFS can traverse the same graph, but it does not naturally guarantee shortest distance in an unweighted graph. BFS does because it processes all nodes at distance 0, then distance 1, then distance 2, and so on.

Common BFS signals:

• "Minimum number of steps"
• "Shortest path" with unweighted edges
• "Nearest exit," "nearest zero," or "closest gate"
• "Level order" in a tree
• "Rotting oranges," "walls and gates," or infection spread
• "Word ladder" transformations
• "All nodes distance K"
• "Multi-source" starting points

The basic state is a queue plus a visited structure. Push the starting node, mark it visited, then repeatedly pop from the queue and add valid neighbors. Distance can be tracked by levels, by storing (node, distance) pairs, or by writing distance into a grid.

Level-order traversal: BFS for trees

Tree level-order traversal is the cleanest BFS version. You start with the root in a queue. While the queue is not empty, capture the current queue size. That size represents one level. Pop exactly that many nodes, collect their values, and push their children. Then move to the next level.

The queue-size trick matters. If you loop until the queue is empty without separating levels, you can traverse the tree but lose level boundaries. Problems like Binary Tree Level Order Traversal, Zigzag Level Order, Right Side View, and Average of Levels all depend on knowing which nodes belong to the current level.

Talk track:

"Because the problem asks for level order, I will use a queue. At the start of each while-loop iteration, the queue contains exactly the nodes for the current level. I will store its length, process that many nodes, enqueue children for the next level, then append the level result."

For right-side view, the last node processed in each level is visible. For minimum depth, the first leaf reached by BFS gives the answer because BFS reaches shallower leaves before deeper leaves. For zigzag traversal, collect a level and reverse it on alternating levels or append values into a deque from different sides.

Unweighted shortest path: why BFS beats DFS

When each move costs one step, BFS finds the shortest path because it expands all paths of length d before any path of length d + 1. This is the key proof interviewers expect.

Examples include shortest path in a binary matrix, nearest exit from entrance in a maze, minimum knight moves, open lock, and word ladder. In each case, a node represents a state: a grid cell, board position, lock combination, or word. Edges represent one legal move or transformation.

A good shortest-path BFS template:

1. Validate the start state.
2. Initialize queue with the start and distance 0 or 1, depending on problem definition.
3. Mark the start visited immediately.
4. Pop a state.
5. If it is the target, return distance.
6. Generate valid neighbors.
7. For each unvisited neighbor, mark visited and enqueue with distance + 1.
8. If the queue empties, return -1 or the problem's failure value.

Marking visited when enqueuing is important. If you wait until popping, the same node can be enqueued many times by different parents at the same level. That wastes time and can cause memory blowups. The first time BFS reaches a node is already the shortest path to that node in an unweighted graph.

Grid BFS: boundaries, directions, and mutation

Grid BFS problems use cells as nodes and adjacent cells as edges. Keep a directions array such as up, down, left, right. For each neighbor, check boundaries, walls or blocked cells, and visited state.

Common grid problems:

• Shortest Path in Binary Matrix
• Rotting Oranges
• Walls and Gates
• Number of Islands variations
• 01 Matrix
• Pacific Atlantic Water Flow, though that one often uses reverse traversal
• Nearest Exit from Entrance in Maze

For grids, visited can be a separate boolean set or you can mutate the grid when allowed. Mutating is efficient and common, but only do it if the problem does not require preserving the input. For example, in Rotting Oranges, changing fresh oranges to rotten as they enter the queue doubles as a visited marker.

Boundary mistakes are common. Say the validation order clearly: "For each neighbor, I check row and column bounds, then whether the cell is passable and unvisited, then mark it visited and enqueue."

Multi-source BFS: start from all sources at once

Multi-source BFS is the pattern that unlocks many medium problems. Instead of starting from one node, push every source node into the queue at distance zero. BFS then expands outward simultaneously, so the first time a target cell is reached, it has the distance to the nearest source.

Examples:

• Rotting Oranges: all rotten oranges start at minute 0.
• 01 Matrix: all zeros start at distance 0, fill distances to ones.
• Walls and Gates: all gates start at 0, fill rooms with nearest gate distance.
• Map of Highest Peak: all water cells start at height 0.
• As Far from Land as Possible: all land cells start as sources, expand into water.

The most common mistake is running BFS separately from every source. That can turn a linear problem into a much slower repeated search. Multi-source BFS solves all distances in one pass.

Talk track:

"Because every source spreads at the same rate, I will enqueue all sources first with distance zero. Then standard BFS guarantees each cell is assigned the nearest source distance the first time it is reached."

Word Ladder and implicit graphs

Not every graph is given as an adjacency list. In Word Ladder, each word is a node, and edges connect words that differ by one character. You can generate neighbors by changing each character position to a through z and checking whether the candidate exists in the word set. BFS is appropriate because each transformation has equal cost and the question asks for the shortest transformation sequence length.

The naive neighbor generation can be expensive. A common optimization is building wildcard patterns: hot becomes ot, ht, and ho*. Words sharing a pattern are neighbors. That reduces repeated scanning of the whole word list.

Important detail: remove or mark words as visited when enqueued. Otherwise the same word can be discovered through many paths. For Word Ladder II, where all shortest paths are required, you need more careful level-based visited handling so you do not delete alternatives within the same level too early. That distinction is a good senior-level signal.

BFS with state: keys, masks, and constraints

Some BFS problems require more than position as state. If the ability to move depends on keys collected, obstacles eliminated, or remaining resources, visited must include those variables.

Examples:

• Shortest Path to Get All Keys: state is row, column, and key mask.
• Shortest Path in a Grid with Obstacles Elimination: state is row, column, and remaining eliminations.
• Open Lock: state is the lock combination.
• Sliding Puzzle: state is the board encoding.

The trap is marking only the position visited. Reaching the same cell with more keys or more obstacle eliminations is not equivalent to reaching it with fewer. Your visited key should reflect the full state that affects future moves.

Interview phrasing:

"I cannot mark only the cell visited because the future options depend on the keys collected. I will store (row, col, keyMask) in visited. That increases the state space, but it preserves correctness."

When BFS is not enough

BFS finds shortest paths only when all edges have equal weight. If moves have different costs, use Dijkstra's algorithm or 0-1 BFS when weights are only 0 and 1. If the graph can have negative edges, shortest-path logic changes again, though LeetCode interview prompts rarely go there for standard BFS questions.

If the problem asks whether a path exists, DFS or BFS can both work. Pick the one that fits the follow-up. If the interviewer asks for shortest path, BFS. If they ask for connected components or exhaustive traversal, either can work. If recursion depth is a concern, iterative BFS may be safer than recursive DFS.

Also watch memory. BFS can hold an entire frontier, which may be large. DFS may use less memory on narrow graphs. In interviews, it is enough to say time is O(V + E) for explicit graphs and memory is O(V) for the queue and visited set, with grid equivalents O(rows * cols).

Common BFS mistakes

Marking visited too late: Mark when enqueuing, not when popping, unless a special shortest-path variant requires level handling.

Forgetting level boundaries: If the output is grouped by level or minute, process fixed queue sizes per layer.

Starting from the wrong side: Nearest-source problems are often easier from all sources than from every target.

Using DFS for shortest path: DFS may find a path, but not necessarily the shortest one.

Not including full state in visited: Position alone is wrong when keys, remaining jumps, obstacle eliminations, or mode changes matter.

Off-by-one distance: Decide whether the start counts as step 0 or path length 1. Match the problem statement and examples.

Using BFS on weighted graphs: Standard BFS assumes equal edge cost.

Interview explanation template

Use this structure under pressure:

"This is an unweighted shortest-path or level-order problem, so BFS is appropriate. I will put the starting state or all starting sources in a queue, mark them visited immediately, and process the queue level by level. Each expansion considers valid neighbors. The first time I reach the target, BFS guarantees the shortest distance because all states at distance d are processed before distance d + 1. The time complexity is linear in the number of states and transitions, and memory is linear in the visited set and frontier."

Then adapt it. For a tree, talk about levels. For a grid, talk about directions and boundaries. For multi-source, talk about simultaneous expansion. For stateful BFS, define the full state tuple.

Practice order for BFS prep

A good sequence:

1. Binary Tree Level Order Traversal
2. Binary Tree Right Side View
3. Minimum Depth of Binary Tree
4. Rotting Oranges
5. 01 Matrix
6. Walls and Gates
7. Shortest Path in Binary Matrix
8. Nearest Exit from Entrance in Maze
9. Open Lock
10. Word Ladder
11. Shortest Path to Get All Keys
12. Shortest Path in a Grid with Obstacles Elimination

After each problem, write down the state, neighbors, visited rule, and distance rule. That four-line review is more valuable than memorizing code.

BFS interviews are about recognizing distance layers. If all moves cost the same and the prompt says closest, fewest, nearest, level, or spread, reach for the queue. Define the state completely, mark visited at the right time, process levels when needed, and explain the shortest-path guarantee. That is the pattern behind most BFS LeetCode questions.

Related guides

• Tree Traversal LeetCode Pattern Guide — Preorder, Inorder, Postorder, and Level-Order — A tree traversal LeetCode pattern guide for choosing preorder, inorder, postorder, or level-order based on the information flow of the problem. Includes templates, traps, interview language, and resume-friendly framing.
• Graph Algorithms LeetCode Pattern Guide — DFS, BFS, Dijkstra, and Union-Find — A practical graph algorithms LeetCode pattern guide covering DFS, BFS, Dijkstra, union-find, topological sort, grid graphs, and interview explanation patterns. Use it to identify the graph shape before choosing the algorithm.
• Backtracking LeetCode Pattern Guide — Permutations, Combinations, and Subsets — A practical backtracking LeetCode pattern guide with templates, decision rules, duplicate-handling tricks, pruning advice, and interview talk tracks for permutations, combinations, subsets, and constraint problems.
• Binary Search LeetCode Pattern Guide — Bounds, Rotated Arrays, and Search-on-Answer — A binary search LeetCode pattern guide for exact search, lower/upper bounds, rotated arrays, and search-on-answer problems. Includes invariants, templates, traps, and interview-ready explanations.
• Bit Manipulation LeetCode Pattern Guide — XOR Tricks, Masks, and Counting Bits — A practical bit manipulation LeetCode pattern guide covering XOR tricks, masks, counting bits, subset enumeration, flags, and the interview pitfalls around signed integers.