Top 13 BFS Problems for Coding Interviews, Ordered by Pattern

You know the queue. You know it explores level by level. You've read the explanation, maybe written BFS from scratch. Then the interviewer says "Rotting Oranges" and your brain just... stalls. Because the oranges start from multiple cells at once and for a second you're not sure whether that counts as BFS or something more exotic.

It's BFS. You just haven't seen all the costumes it wears yet.

This guide covers 13 BFS problems ordered by pattern family, not raw difficulty. Work through them in sequence and you'll build a mental map that transfers to new problems. The code confirms your understanding. It doesn't replace it.

Problem 1 Sets the Foundation: Binary Tree Level Order Traversal

LeetCode 102. The canonical entry point. Enqueue root, dequeue a node, enqueue its children, repeat. The detail that separates strong candidates is the level snapshot.

from collections import deque

def levelOrder(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):   # snapshot size before adding children
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

The for _ in range(len(queue)) loop is the move. You snapshot the queue size before processing any node in the current level, so you know exactly when one level ends and the next begins. It looks like an innocent loop. It is actually doing all the level-tracking work. Every level-order variant reuses this frame: zigzag traversal (LC 103), right side view (LC 199), minimum depth (LC 111). Learn it once, apply it everywhere.

BFS level snapshot diagram: how snapshotting len(queue) creates clean level boundaries

Grid BFS Problems All Share One Frame

LeetCode 200. Number of Islands. Scan the grid, and whenever you land on an unvisited '1', run BFS outward to mark the entire connected island. Count how many times you start that BFS.

The outer scan loop is not optional. Grids can have multiple disconnected regions. Skip the outer loop and you find one island, then stop. Every grid BFS that counts connected components needs this two-level structure: outer loop finds seeds, inner BFS floods each one.

LeetCode 994. Rotting Oranges. All rotten oranges enter the queue together at time zero and expand simultaneously. Nothing about the BFS loop changes. The only difference is that you seed multiple start nodes before the loop begins, not one. That's it. That's the whole trick.

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue, fresh = deque(), 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2: queue.append((r, c, 0))
            elif grid[r][c] == 1: fresh += 1
    time = 0
    while queue:
        r, c, t = queue.popleft()
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh -= 1
                queue.append((nr, nc, t+1))
                time = max(time, t+1)
    return time if fresh == 0 else -1

"Multi-source BFS" sounds like a different algorithm. It isn't. It's regular BFS with multiple start nodes queued before the loop begins. The queue processes them in arrival order, which automatically interleaves the frontiers from every source.

Multi-Source BFS Runs One Pass, Not One Per Cell

LeetCode 542. 01 Matrix. Find the distance from each cell to the nearest 0. The wrong approach: BFS from each 1 individually. That's O(mn) per cell, and you'll get a TLE for your trouble.

The right approach seeds all 0s simultaneously and propagates distances outward in a single pass.

def updateMatrix(mat):
    rows, cols = len(mat), len(mat[0])
    dist = [[float('inf')] * cols for _ in range(rows)]
    queue = deque()
    for r in range(rows):
        for c in range(cols):
            if mat[r][c] == 0:
                dist[r][c] = 0
                queue.append((r, c))
    while queue:
        r, c = queue.popleft()
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] > dist[r][c] + 1:
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))
    return dist

Walls and Gates (LC 286) has the same structure: seed all gates, expand outward assigning distances. Two problems with different descriptions, one skeleton. Recognizing that pattern is worth more than any individual solution.

When Forward Simulation Is Expensive, Run It Backward

LeetCode 417. Pacific Atlantic Water Flow. Water flows downhill. You want cells that can reach both the Pacific (top and left border) and the Atlantic (bottom and right border). Simulating forward from each cell is O(m²n²). Nobody has time for that.

Reverse the direction. Run BFS inward from each ocean's border, moving uphill instead of downhill. Cells appearing in both BFS results are your answer. The graph is the same. You only flipped who starts and which direction counts as valid. This pattern comes up whenever forward simulation from every source is too expensive and you can work inward from a known boundary instead.

LeetCode 1091. Shortest Path in Binary Matrix. Eight-directional grid BFS. Add all 8 neighbors (diagonals included) instead of 4. Nothing else changes. If you need the shortest path in an unweighted graph, BFS gives you the guarantee. DFS does not. DFS finds a path. Not necessarily the shortest one.

State Space BFS: The Graph Has No Coordinates

This is where people's eyes go wide. No grid. No tree. The nodes are strings.

LeetCode 127. Word Ladder. An edge exists between two words if they differ by exactly one character. You want the shortest transformation sequence from start to end. The graph is implicit. You build it on the fly by trying every character substitution.

def ladderLength(beginWord, endWord, wordList):
    word_set = set(wordList)
    if endWord not in word_set: return 0
    queue = deque([(beginWord, 1)])
    visited = {beginWord}
    while queue:
        word, length = queue.popleft()
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                new_word = word[:i] + c + word[i+1:]
                if new_word == endWord: return length + 1
                if new_word in word_set and new_word not in visited:
                    visited.add(new_word)
                    queue.append((new_word, length + 1))
    return 0

"Reachable in one transformation" defines edges in an implicit graph, and BFS over that graph finds the shortest path. The visited set holds strings. Everything else is identical to grid BFS.

LeetCode 752. Open the Lock. Four wheels, each 0-9. Reach a target combination while avoiding dead ends. The state is a 4-digit string. Each state has 8 neighbors (each wheel can go up or down). BFS over states finds minimum turns.

The structure is identical to Word Ladder. The domain is completely different. Both become routine once you can see "string as a node in an implicit graph." Before that click, both problems look like magic. After it, they look like the same problem.

Topological BFS Answers Dependency Questions

LeetCode 207. Course Schedule. Detect whether a dependency graph has a cycle. Kahn's algorithm: track in-degree counts, queue all zero-in-degree nodes, process them, decrement neighbors, enqueue any that reach zero. Cycle detection comes for free.

def canFinish(numCourses, prerequisites):
    in_degree = [0] * numCourses
    graph = [[] for _ in range(numCourses)]
    for dest, src in prerequisites:
        graph[src].append(dest)
        in_degree[dest] += 1
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    processed = 0
    while queue:
        node = queue.popleft()
        processed += 1
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return processed == numCourses

If all nodes get processed, there's no cycle. If any remain with non-zero in-degree, they are stuck in a cycle. You do not check explicitly. The count tells you.

LeetCode 310. Minimum Height Trees. Find the roots that minimize tree height. The algorithm: repeatedly prune all current leaf nodes (degree 1) until 1 or 2 remain. Those are your answers. This is Kahn's algorithm where "degree 1" plays the role of "in-degree 0." Same queue mechanics, completely different framing. Once you see it, you can't unsee it.

The Hard Tier Forces You to Rethink the Graph

These three problems share a root cause: candidates model the graph incorrectly, write perfectly clean BFS over the wrong structure, and get the wrong answer.

LeetCode 815. Bus Routes. Minimum buses to reach the target stop. The trap: treating bus stops as nodes. That finds minimum stops, not minimum transfers. Those are different problems.

The fix: treat each route as a node, not each stop. Two routes connect if they share a stop. Build a map from stop to all routes that serve it. BFS state is a route index. Level count is transfers. Once you shift the model, the BFS writes itself. This is the most common "rethink what a node is" problem in real interviews, and missing it looks bad because your code will be clean and confident and completely wrong.

LeetCode 909. Snakes and Ladders. Minimum dice rolls to reach the last square. BFS over board positions 1 to n*n, up to 6 neighbors per state. The only real difficulty is coordinate math: converting a 1-indexed linear position to the actual row and column in the zigzag layout. Work that mapping out on paper first. The BFS is trivial once it's right.

LeetCode 773. Sliding Puzzle. A 2x3 board. Six tiles. Reach the target configuration in minimum moves. State is the board serialized as a string like "123450". BFS over state strings with the blank tile swapping into valid neighbors. Precompute which flat indices are adjacent to each blank position in the 2x3 grid, since adjacency changes depending on where the blank sits. If you solve this cold, you own state-space BFS. It shows up at Google and Meta.

Lock These In

LC 102, LC 200, and LC 994 are mandatory first. Do not skip ahead.
Multi-source BFS (LC 994, LC 542): seed all sources at once and run one pass. Running BFS from each source separately walks the same territory multiple times and earns you a TLE.
Reverse BFS (LC 417): the move when forward simulation from every cell is too expensive. Same graph, flipped start and direction.
State-space BFS (LC 127, LC 752, LC 773): visited set operates on serialized state, not coordinates. Strings, tuples, and frozensets all work as keys.
Topological BFS (LC 207, LC 310): in-degree arrays, cycle detection automatic via processed count.
LC 815 Bus Routes is the most common "rethink the node" problem in interviews. What you model as a node changes everything.

Before your next interview, work these problems in order without peeking at solutions. Verbalize the pattern before writing code. Interviewers score pattern identification separately from implementation, and "I recognize this as state-space BFS because the state is a string and I need shortest transformation" lands better than silently typing the right answer. If you want structured reps at that verbalization under time pressure, SpaceComplexity runs voice-based mock interviews that push you to name the algorithm and justify it before you touch the keyboard.

For the theory behind why BFS guarantees shortest paths in unweighted graphs while DFS does not, see BFS vs DFS. For the five signal patterns that tell you when a problem wants BFS, see BFS Pattern Recognition. When topological sort appears in a problem, Topological Sort Algorithm covers Kahn's in depth. For graph representation fundamentals, Graph Data Structure Interview is the place to start.