Coding interview pattern
Breadth-First Search (BFS)
Explore level by level with a queue; the natural fit for shortest paths on unweighted graphs.
The idea
How the breadth-first search (bfs) pattern works
Breadth-first search explores a graph or tree outward in concentric layers: all nodes at distance one from the start, then all at distance two, and so on. It uses a queue (first in, first out) and a visited set, dequeuing a node, processing it, and enqueuing its unvisited neighbours. Because it reaches nodes in nondecreasing order of distance, BFS finds the shortest path in any unweighted graph, which is its signature use.
The level-by-level property is also what makes BFS the tool for tree level-order traversal and for any problem phrased as fewest steps, minimum moves, or nearest something. A common trick is to record the queue size at the start of each iteration so you can process exactly one full level at a time, which is how you tag each node with its depth or emit one list per tree level.
Multi-source BFS generalises the idea: seed the queue with several starting nodes at once and the search computes the distance from each node to its nearest source in a single pass. This solves grid problems like rotting oranges or walls and gates far more cleanly than running BFS from every cell separately.
Recognition
When to reach for it
- You need the shortest path or minimum number of steps on an unweighted graph or grid.
- You want to process a tree level by level.
- The problem says fewest moves, minimum transformations, or nearest.
- Several sources spread simultaneously (multi-source BFS).
Cost
Time & space complexity
| Operation | Time | Space |
|---|---|---|
| Graph BFS | O(V + E) | O(V) |
| Grid BFS (r x c) | O(r*c) | O(r*c) |
| Tree level-order | O(n) | O(width) |
Worked example
Walkthrough: Shortest path in a binary grid
- 1Enqueue the start cell with distance 1 and mark it visited.
- 2Dequeue a cell; if it is the target, return its distance.
- 3For each of its open, in-bounds, unvisited neighbours, mark them visited and enqueue them with distance plus one.
- 4Marking visited at enqueue time, not dequeue time, prevents the same cell being queued twice.
- 5If the queue empties without reaching the target, no path exists.
Translatable skeleton
The shape in pseudocode
Language-agnostic on purpose. Translate it to your language of choice.
queue = [start]; visited = {start}; while queue: node = queue.popleft(); for nb in neighbours(node): if nb not in visited: visited.add(nb); queue.append(nb)Practice
Curated problem set
Work these in order, easy to hard. Each is chosen to drill a different facet of the pattern.
| Problem | Level | Why it fits |
|---|---|---|
| Binary Tree Level Order Traversal | Medium | Process one level per queue snapshot. |
| Number of Islands | Medium | BFS flood fill on a grid. |
| Rotting Oranges | Medium | Multi-source BFS over time steps. |
| Word Ladder | Hard | BFS over a word-transformation graph. |
| Shortest Path in Binary Matrix | Medium | 8-directional grid BFS. |
| 01 Matrix | Medium | Multi-source BFS from all zeros. |
Avoid these
Common pitfalls
- Marking visited on dequeue instead of enqueue, causing duplicates and TLE.
- Using BFS on a weighted graph where Dijkstra is required.
- Forgetting the level-size snapshot when depth matters.
- Mutating the queue while iterating a level.
In the interview
How to communicate it live
Recognising the pattern is half the score; saying the right things out loud is the other half. These are the sentences that earn the signal.
Justify the choice of BFS over DFS by naming the keyword in the prompt, usually shortest, fewest, or minimum steps; BFS is correct for those on unweighted graphs precisely because it visits in order of distance.
Call out explicitly that you mark nodes visited at enqueue time, not dequeue time, and explain that this is what prevents the same node being queued twice and blowing up the runtime.
If the problem needs the depth or one list per level, mention the trick of snapshotting the queue size at the start of each loop so you process exactly one level at a time.
Also searched as
bfs traversal - level order traversal - shortest path unweighted graph
Last reviewed by the site editor: June 2026
An external resource we recommend. AlgoExpert is not affiliated with us and we earn nothing from this link.
Sources
- 4.1 Undirected Graphs (breadth-first search) Sedgewick and Wayne, Princeton University
- Lecture 9: Breadth-First Search MIT OpenCourseWare, 6.006 Introduction to Algorithms
- Tree traversal (level order) Wikipedia
Next up
Patterns that pair well with this one
Real problems rarely match a single pattern. Interviewers like to combine this one with these.
- Sliding Window
Track a contiguous subarray or substring without re-scanning it from scratch.
- Two Pointers
Walk two indices toward or alongside each other to avoid a nested loop.
- Binary Search
Halve the search space each step over any monotonic condition, not just sorted arrays.
- Dynamic Programming
Solve overlapping subproblems once, store the results, and build the answer up.
Round out your prep
See all coding patterns, the coding questions for your role, and the behavioral round.