Breadth-First Search vs Depth-First Search
Shortest Steps in Unweighted Graphs vs Branch Exhaustion and Recursion Hazards
Choosing between queue-based layer expansion and recursive depth traversal, including recursion depth limits and Kahn's topological sort.
"Are you finding the shortest path in an unweighted structure, or are you validating complete subtree properties and connectivity?"
Ask this single question during the first two minutes of reading the problem prompt. The answer decides your fundamental pattern.
Drop a small pebble into a still temple tank. Ripples expand outward in concentric circles. Every point at distance 1 gets wet first, then distance 2, then distance 3. If you want to find the closest lotus flower to the pebble, the ripple hits it first (BFS: layer-by-layer expansion guarantees the shortest step count). Now picture a speleologist exploring a deep limestone cave with a single spool of thread tied to the entrance. She follows one narrow tunnel as deep as it goes until she hits solid rock, then winds the thread back up to the last fork and tries the next branch (DFS: depth-first search explores an entire branch before backtracking).
When to Choose Which Pattern
Breadth-First Search (BFS)
Option A- ✓Shortest path or minimum moves in an unweighted graph, grid, or state transition game.
- ✓Multi-source spreading problems (e.g. rotting oranges, fire spreading, infection propagation).
- ✓Level-order traversal of trees where results are grouped by depth.
- ✓Topological sorting using Kahn's in-degree queue algorithm (avoids recursion call-stack overflow).
Depth-First Search (DFS)
Option B- ✓Connected components count (e.g. Number of Islands, Number of Provinces).
- ✓Tree property validation (e.g. Subtree of Another Tree, Max Depth, Symmetric Tree).
- ✓Path existence and maze exploration where any valid path is sufficient.
- ✓Backtracking problems where choices are explored and undone.
Side-by-Side Worked Examples
Compare concrete implementations side by side to see how the code structure diverges.
Rotting Oranges(LC 994)
LeetCode ↗All initially rotten oranges start in the queue at minute 0 (multi-source BFS). Each minute, process the current queue size, spreading rot to 4-directionally adjacent fresh oranges and decrementing fresh count. When the queue is empty, if fresh oranges remain, return -1; otherwise return elapsed minutes.
from collections import deque
def orangesRotting(grid: list[list[int]]) -> int:
rows, cols = len(grid), len(grid[0])
q = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
q.append((r, c))
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while q and fresh > 0:
minutes += 1
for _ in range(len(q)):
r, c = q.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
q.append((nr, nc))
return minutes if fresh == 0 else -1Number of Islands(LC 200)
LeetCode ↗Iterate across the grid. When an unvisited land cell '1' is found, increment island count and trigger a DFS flood-fill that recursively marks all 4-way adjacent land cells as visited. DFS visits the entire connected component with minimal boilerplate code.
def numIslands(grid: list[list[str]]) -> int:
if not grid: return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0'
dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return countThe Decision Matrix
Shortest Path Guarantee
Guaranteed in unweighted graphs upon first visit
No guarantee (must visit all paths to find shortest)
Data Structure
Queue (FIFO)
Call Stack (recursion) or explicit Stack (LIFO)
Memory Bound
O(W) proportional to graph/tree maximum width
O(H) proportional to graph/tree maximum depth
Recursion Risk
None (runs iteratively)
High risk on deep paths (Python 1000 limit, JVM stack overflow)
| Evaluation Factor | Breadth-First Search (BFS) | Depth-First Search (DFS) |
|---|---|---|
| Shortest Path Guarantee | Guaranteed in unweighted graphs upon first visit | No guarantee (must visit all paths to find shortest) |
| Data Structure | Queue (FIFO) | Call Stack (recursion) or explicit Stack (LIFO) |
| Memory Bound | O(W) proportional to graph/tree maximum width | O(H) proportional to graph/tree maximum depth |
| Recursion Risk | None (runs iteratively) | High risk on deep paths (Python 1000 limit, JVM stack overflow) |
Where Candidates Go Wrong (Top Traps)
Using DFS to find shortest path in a grid
Marking nodes visited when popping instead of when pushing in BFS
Python recursion limit on deep graphs
Related Walkthroughs in our DSA Course
Explore step-by-step solutions with 4-language code flaps (Java, C#, TS, Python) and visual memory dry runs.
Rotting Oranges (Multi-Source BFS)
Tree BFS and Level Order Primer
Binary Tree Level Order Traversal
Subtree of Another Tree (DFS Tree Matching)
Number of Provinces (Graph Connectivity)
"BFS guarantees shortest paths in unweighted graphs and layer structures, but consumes memory proportional to the widest layer. DFS consumes minimal memory on deep balanced structures, but cannot guarantee shortest paths without exhaustive search and risks call stack overflow on deep paths."
Practice Real Indian Hiring Loops
See the exact problems asked at Flipkart, Swiggy, Razorpay, PhonePe, and Amazon with verified candidate reports and round structures.