BFS Leetcode and DFS Patterns — When to Use Each in Interviews

Every LeetCode graph or tree problem can technically be solved with either BFS or DFS. That flexibility is the trap. When you reach for the wrong traversal, the code that should take 15 lines baloons to 40 — you are fighting the algorithm instead of using it. The engineers who consistently ace graph problems in interviews are not smarter; they have internalized a simple decision framework that tells them which traversal fits the problem before writing a single line of code.

BFS and DFS are not interchangeable tools that happen to produce different outputs — they have fundamentally different guarantees. BFS processes nodes level by level and guarantees the shortest path in an unweighted graph. DFS dives as deep as possible along each branch and guarantees that every reachable node is visited, making it natural for connectivity and path problems. Swapping them on the wrong problem type does not just add complexity; it can produce subtly wrong answers that are hard to debug under interview pressure.

In LeetCode interviews, BFS appears most often in tree-level problems and graph shortest-path problems, while DFS dominates island/connected-component and all-paths problems — knowing this split covers roughly 40% of all LeetCode graph questions. This guide breaks down the exact patterns, gives you a 5-question decision framework, and walks through the canonical problems for each category so you can pattern-match on sight.

Breadth-first search uses a queue (FIFO) to process nodes in the order they were discovered. At each step, you dequeue the front node, process it, and enqueue all unvisited neighbors. Because you always process nodes in discovery order, all nodes at distance 1 are processed before any node at distance 2, all distance-2 nodes before distance-3, and so on. This level-by-level property is not a cosmetic detail — it is the fundamental guarantee that makes BFS correct for shortest-path problems.

The canonical BFS template in Python is: initialize a queue with the starting node(s), mark them visited, then loop while the queue is non-empty — dequeue, process, enqueue unvisited neighbors and mark them visited immediately on enqueue (not on dequeue, which is a common bug). For level-tracking, wrap the inner loop in an outer loop that processes exactly queue.size() nodes per iteration, incrementing a level counter after each batch.

BFS guarantees the shortest path in an unweighted graph because it explores nodes level by level — using DFS for shortest path problems requires backtracking and runs in O(V!) in the worst case, making BFS 10,000x faster on typical interview inputs. This asymmetry is why BFS is the mandatory choice for any problem asking for "minimum steps," "minimum moves," or "shortest path" in an unweighted setting.

The visited set in BFS must be populated on enqueue, not on dequeue. If you mark a node visited when you dequeue it, the same node can be added to the queue multiple times before it is processed — on dense graphs this degrades from O(V + E) to O(V * E) and causes TLE on LeetCode. This is one of the most common BFS bugs in real interview settings.

Depth-first search explores as far as possible along each branch before backtracking. It can be implemented recursively (using the call stack) or iteratively (using an explicit stack). Recursive DFS is cleaner and more idiomatic for tree problems. Iterative DFS is necessary when recursion depth could exceed Python's default limit of ~1000 — relevant on large grid problems like a 300x300 matrix where DFS could stack-overflow with the recursive approach.

The canonical recursive DFS template: mark the current node visited, then for each unvisited neighbor, recurse. The key decision is whether to pass the visited set through parameters (stateless, for tree problems where nodes are not revisited) or maintain it as external state (for graph problems). For backtracking variants — where you need to explore all paths and undo choices — you mark visited before the recursive call and unmark after it returns.

DFS is the natural fit when the problem asks about connectivity, path existence, or enumerating all paths — because DFS naturally follows a single path to completion before trying alternatives. When you need to know "can I reach node B from node A," DFS finds the answer as soon as it touches B, without necessarily processing the entire graph. When you need to count connected components, DFS from each unvisited node gives you exactly one component per DFS invocation.

The tradeoff between recursive and iterative DFS on LeetCode: recursive is faster to write and easier to reason about during interviews; iterative is safer for large inputs and avoids RecursionError. For tree problems (depth usually < 100), always use recursive. For grid problems with large dimensions (200x200 grid = 40,000 nodes), prefer iterative or bump Python's recursion limit with sys.setrecursionlimit(200000).

The clearest BFS signal in a problem statement is any mention of "shortest," "minimum steps," "minimum moves," or "fewest operations" in an unweighted setting. Rotting Oranges (LeetCode #994) is the canonical multi-source BFS problem: all initially rotten oranges are seed nodes, and BFS propagates the rot level by level, counting the number of levels (minutes) until all fresh oranges are rotten. Attempting this with DFS produces incorrect minimum time because DFS does not process nodes in distance order.

Snakes and Ladders (LeetCode #909) is a BFS-on-implicit-graph problem where the state is the current board position and each BFS level represents one dice roll. The board's snakes and ladders are just teleportation edges in the graph — BFS correctly finds the minimum number of dice rolls to reach the last cell. Open the Lock (LeetCode #752) follows the same pattern: each state is a 4-digit combination, each BFS neighbor is one digit increment or decrement, and BFS finds the minimum number of turns to reach the target combination.

Binary tree level-order traversal (LeetCode #102) is the tree-specific BFS pattern where the level counter directly tells you which row each node belongs to. The output is a list of lists grouped by level — something that is trivially available from BFS (just count nodes per queue flush) but requires extra bookkeeping with DFS. Any problem asking for "rightmost node per level" (LeetCode #199), "average per level," or "zigzag level order" is a BFS level-traversal variant.

Word Ladder (LeetCode #127) is the most sophisticated BFS pattern: the graph is implicit (no explicit edge list is given), and you construct edges on the fly by trying all single-character mutations of the current word and checking if the result is in the word list. BFS on this implicit graph finds the shortest transformation sequence in O(M² × N) where M is word length and N is the word list size.

The clearest DFS signal is a problem asking you to count connected components, detect cycles, find if a path exists, or explore all possible paths. Number of Islands (LeetCode #200) is the canonical DFS connected-components problem: iterate over the grid, and for each unvisited land cell, trigger a DFS that marks all connected land cells as visited — each DFS invocation from an unvisited cell adds one to the island count. This is the template for all flood-fill and component-counting problems.

Pacific Atlantic Water Flow (LeetCode #417) uses reverse DFS from both oceans simultaneously. Instead of DFS from every cell asking "can water reach both oceans?" (which is O(V²)), you DFS from all Pacific-border cells marking "reachable from Pacific" and separately DFS from all Atlantic-border cells marking "reachable from Atlantic," then return the intersection. This reverse-traversal trick appears in several DFS problems where the naive forward direction is too slow.

Clone Graph (LeetCode #133) uses DFS with a hash map from old nodes to new nodes. The DFS visits each node once, creates a clone, and recursively clones all neighbors before returning. The hash map serves as both the visited set and the mapping from original to clone — a two-in-one data structure that prevents infinite recursion and enables correct neighbor assignment simultaneously.

Cycle detection in directed graphs (Course Schedule, LeetCode #207) uses DFS with a three-color visited state: unvisited (0), in-progress (1), and completed (2). A cycle exists if DFS encounters a node currently in-progress — meaning you have found a back edge. This is more nuanced than undirected cycle detection and is a frequent interview topic because candidates who only know undirected cycle detection fail on directed graph variants.

After internalizing hundreds of graph problems, the pattern comes down to five questions you ask in order. The first question to ask: does the problem ask for shortest path or minimum steps in an unweighted graph? If yes, the answer is always BFS — no exceptions. DFS cannot solve unweighted shortest path correctly without exponential backtracking.

The second question: does the problem ask for level-by-level processing, something per tree level, or anything described as "waves" spreading outward? BFS processes nodes exactly in level order, making level-indexed information trivially available. DFS can compute this information but requires extra bookkeeping (depth parameter in recursion or explicit level tracking in iterative DFS).

The third question: does the problem ask to count connected components, detect cycles, or determine if two nodes are connected? These are all DFS-native problems. DFS naturally delineates components by the scope of each recursive call. Flood fill, island counting, and region coloring all follow the same DFS component template.

The fourth question: does the problem ask to find all possible paths or enumerate all solutions? DFS with backtracking is the right tool — BFS does not naturally enumerate paths because it processes nodes without maintaining the full path history.

The fifth question: if none of the above apply and the problem involves a graph with weights, reach for Dijkstra (for non-negative weights) or Bellman-Ford (for negative weights) rather than either BFS or DFS. BFS shortest-path only works on unweighted (or uniformly-weighted) graphs — the moment edge weights differ, BFS gives wrong answers.

The most costly mistake on BFS problems is marking nodes visited on dequeue instead of enqueue. In a dense graph, the same node can be added to the queue O(degree) times before it is first dequeued. On a grid problem with a 200x200 matrix, this turns an O(V + E) solution into O(V * E) — producing TLE on LeetCode even though the logic is otherwise correct. Fix: call visited.add(neighbor) immediately before queue.append(neighbor), not at the start of the dequeue loop.

On DFS problems, forgetting to restore state during backtracking is a silent bug that causes wrong answers without errors. In problems like Word Search (LeetCode #79) where you mark cells visited in-place (board[r][c] = "#"), you must restore the cell to its original value after the recursive call returns. Without restoration, later DFS branches from higher stack frames see an incorrectly modified board and miss valid paths.

Choosing recursive DFS on very large grids without adjusting the recursion limit produces a RecursionError on LeetCode even when the algorithm is correct. A 300x300 grid can trigger 90,000 recursive calls in the worst case — far beyond Python's default 1000. Either use iterative DFS with an explicit stack, or add sys.setrecursionlimit(300 * 300 + 100) at the top of your solution.

On multi-source BFS problems (Rotting Oranges, 01 Matrix), a common mistake is initializing the queue with only one source instead of all sources simultaneously. Single-source BFS on a multi-source problem computes distances from the first source only, not the minimum distance across all sources. Initialize the queue with all source nodes together before starting the BFS loop.

The BFS/DFS decision is not a knowledge problem — it is a pattern recognition problem. Both algorithms are short to implement once you have the templates memorized. The skill that separates interview performers is the ability to classify a novel problem into the correct traversal category within 30 seconds of reading the problem statement. That classification speed comes exclusively from drilling the canonical problems for each category until the patterns are reflexive.

Start with the BFS canonical set: Rotting Oranges (#994), Snakes and Ladders (#909), Open the Lock (#752), and Binary Tree Level Order Traversal (#102). These four problems cover multi-source BFS, BFS on implicit graphs, BFS on state spaces, and BFS on trees respectively — the four major BFS subtypes that appear in interviews. Then drill the DFS canonical set: Number of Islands (#200), Pacific Atlantic Water Flow (#417), Clone Graph (#133), and Course Schedule (#207).

After completing both canonical sets, practice the classification step in isolation: read only the problem title and first paragraph, then write down "BFS" or "DFS" and the reason before reading the full problem. This deliberate classification practice builds the reflexive pattern recognition that makes BFS/DFS problems feel easy in interviews rather than stressful.

YeetCode's spaced repetition system is built specifically for this kind of pattern drilling — it resurfaces BFS and DFS problems at scientifically optimal intervals so your classification reflexes stay sharp through the full length of a job search. The engineers who ace graph problems in FAANG interviews do not re-solve problems from scratch before every interview round; they use spaced repetition to keep the patterns accessible without grinding 8 hours a day.