Pattern 04 · Trees & Graphs
Breadth-First Search
Explore a graph level by level with a FIFO queue: everything at depth d is visited before anything at depth d+1. That one property means the first time BFS reaches a node is the shortest path to it — in unweighted graphs.
time O(V + E)space O(width)variants level · multi-source · state-spacepractice 16 problems
01 core concept
Explore in waves, not dives
BFS visits all nodes at the current depth before moving to the next depth. The engine is a queue (FIFO): pop from the front, push children to the back. Since children always join the back of the line, depth d fully drains before depth d+1 begins.
BFS on a tree -- level by level:
1 Level 0
/ \
2 3 Level 1
/ \ \
4 5 6 Level 2
Queue progression:
Queue: [1] Process 1, add children 2,3
Queue: [2, 3] Process 2, add 4,5. Process 3, add 6
Queue: [4, 5, 6] Process 4, 5, 6 (no children)
Queue: [] Done!
Visit order: 1 -> 2 -> 3 -> 4 -> 5 -> 6
Why BFS gives the shortest path
BFS expands like a WAVEFRONT -- all nodes at distance d
are visited before any node at distance d+1.
Start: S
After 1 step: After 2 steps: After 3 steps:
. .. ...
.S. .SS. .SSS.
. .SS. .SSS.
.. .SS.
.
The first time BFS reaches a node IS the shortest path to it.
Watch the queue do the work on the classic level-order tree
(root 3, children 9 and 20; 20 has
children 15 and 7):
step 1 / 7walkthrough — level-order traversal (LC 102)
queue [3]
result []
Seed the queue with the root. Each pass of the while-loop will process one full level — exactly len(queue) nodes.
02 recognition
When to reach for it
Keyword signals
If the problem says "shortest", "minimum number of steps",
"fewest moves", "closest", "level by level",
or "minimum operations to transform" — think BFS first.
BFS vs. DFS
| Scenario | BFS | DFS |
|---|---|---|
| Shortest path (unweighted) | YES | no |
| Level-order traversal | YES | possible |
| Minimum steps | YES | no |
| All paths enumeration | possible | YES |
| Cycle detection | possible | YES |
| Topological sort | YES (Kahn) | YES |
| Connected components | YES | YES |
| Memory on deep graph | YES | risky |
| Memory on wide graph | risky | YES |
03 strategy
Which flavor of BFS?
Four questions route you to the right variant. The last one is the interview differentiator: in state-space BFS, a "node" is an entire state (a lock combination, a word), not a position.
What am I looking for?
|
+--> Shortest path / min steps?
| |
| +--> Unweighted graph? --> Standard BFS
| +--> Weighted graph? --> Dijkstra (not plain BFS)
| +--> 0/1 weights? --> 0-1 BFS with deque
|
+--> Level-by-level processing?
| |
| +--> Track level size at each iteration
| +--> Process len(queue) nodes per level
|
+--> Multiple starting points?
| |
| +--> Multi-source BFS
| +--> Add ALL sources to queue at start
| +--> Examples: rotting oranges, 01 matrix
|
+--> State-space search?
|
+--> Each "node" is a STATE (not just a position)
+--> Example: Open the Lock -> state = "0000"
+--> Visited set tracks states, not positions
04 templates
The four templates to memorize
T1Tree BFS — level order (LC 102)
The key line is the level-size snapshot: take len(queue)
before the inner loop, and process exactly that many nodes. Everything enqueued
during the loop belongs to the next level.
level_order.pypython
from collections import deque
def level_order(root):
"""BFS level-order traversal. Returns list of lists."""
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue) # KEY: snapshot current level size
level = []
for _ in range(level_size): # process exactly this level
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
# 3
# / \
# 9 20 Result: [[3], [9, 20], [15, 7]]
# / \
# 15 7T2Graph BFS — with visited set
bfs_graph.pypython
from collections import deque
def bfs_graph(graph, start):
"""BFS on adjacency list. Returns visited order."""
visited = {start} # mark BEFORE enqueuing
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor) # mark WHEN enqueuing, not when processing
queue.append(neighbor)
return orderT3Grid BFS — 4-directional
bfs_grid.pypython
from collections import deque
def bfs_grid(grid, start_r, start_c):
"""BFS on a grid. Returns shortest distance to all reachable cells."""
rows, cols = len(grid), len(grid[0])
distances = [[-1] * cols for _ in range(rows)]
distances[start_r][start_c] = 0
queue = deque([(start_r, start_c)])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] # R, L, D, U
while queue:
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
# Check bounds + not visited + not wall
if (0 <= nr < rows and 0 <= nc < cols
and distances[nr][nc] == -1
and grid[nr][nc] != 0):
distances[nr][nc] = distances[r][c] + 1
queue.append((nr, nc))
return distances The grid wavefront in action -- shortest path from S to E:
S . . . . 0 1 2 3 4
. # # . . 1 # # 4 5
. . # . . --> 2 3 # 5 6
. . . . . 3 4 5 6 7
. . . . E 4 5 6 7 8
The first time BFS reaches E, the distance IS the shortest path.
T4Multi-source BFS
When distances are measured to the nearest of several sources, don't run BFS once per source — enqueue all sources at distance 0 and run a single BFS. Same complexity as single-source.
multi_source_bfs.pypython
from collections import deque
def multi_source_bfs(grid, sources):
"""BFS from multiple starting points simultaneously."""
rows, cols = len(grid), len(grid[0])
distances = [[-1] * cols for _ in range(rows)]
queue = deque()
# Add ALL sources to queue at the start
for r, c in sources:
distances[r][c] = 0
queue.append((r, c))
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while queue:
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols
and distances[nr][nc] == -1):
distances[nr][nc] = distances[r][c] + 1
queue.append((nr, nc))
return distances Multi-source BFS is like dropping multiple stones in a pond:
S . . . S 0 1 2 1 0
. . . . . 1 2 3 2 1
. . . . . --> 2 3 4 3 2
. . . . . 1 2 3 2 1
S . . . S 0 1 2 1 0
Each cell gets the distance to the NEAREST source.
05 classic problems
The problems the templates unlock
P1Rotting Oranges (LC 994) — multi-source
All rotten oranges spread simultaneously, one ring per minute — a textbook multi-source BFS. Enqueue every rotten orange with time 0, count the fresh ones, and let the wavefront run:
2 = rotten (R), 1 = fresh (f), 0 = wall (.)
t=0: t=1: t=2: t=3: t=4:
R f f R R f R R R R R R R R R
f f . R f . R R . R R . R R .
. f f . f f . f f . R f . R R
Answer: 4 minutes. If any fresh orange is unreachable
(walled off from every rotten one), return -1.
oranges_rotting.py — LC 994python
def oranges_rotting(grid):
"""Find minimum minutes until all oranges rot. Multi-source BFS."""
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
# Step 1: Find all rotten oranges (sources) and count fresh
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c, 0)) # (row, col, time)
elif grid[r][c] == 1:
fresh += 1
if fresh == 0:
return 0
# Step 2: BFS from all rotten oranges simultaneously
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
time = 0
while queue:
r, c, time = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols
and grid[nr][nc] == 1): # fresh orange
grid[nr][nc] = 2 # now rotten
fresh -= 1
queue.append((nr, nc, time + 1))
return time if fresh == 0 else -1P201 Matrix (LC 542) — multi-source from zeros
"Distance of each cell to the nearest 0" — flip your perspective: don't BFS from every 1, BFS from all the 0s at once.
update_matrix.py — LC 542python
from collections import deque
def update_matrix(mat):
"""Find distance of each cell to nearest 0. Multi-source BFS."""
rows, cols = len(mat), len(mat[0])
queue = deque()
INF = float('inf')
# Initialize: 0 cells have distance 0, others are INF
for r in range(rows):
for c in range(cols):
if mat[r][c] == 0:
queue.append((r, c)) # source
else:
mat[r][c] = INF # to be computed
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while queue:
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols
and mat[nr][nc] > mat[r][c] + 1):
mat[nr][nc] = mat[r][c] + 1
queue.append((nr, nc))
return matP3Shortest Path in Binary Matrix (LC 1091) — 8 directions
shortest_path_binary_matrix.py — LC 1091python
from collections import deque
def shortest_path_binary_matrix(grid):
"""Shortest path from (0,0) to (n-1,n-1) in binary matrix. 8 directions."""
n = len(grid)
if grid[0][0] != 0 or grid[n-1][n-1] != 0:
return -1
queue = deque([(0, 0, 1)]) # (row, col, distance)
grid[0][0] = 1 # mark visited
# 8 directions (including diagonals)
directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
while queue:
r, c, dist = queue.popleft()
if r == n - 1 and c == n - 1:
return dist
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
grid[nr][nc] = 1 # mark visited
queue.append((nr, nc, dist + 1))
return -1P4Word Ladder (LC 127) — state-space BFS
Here the graph is implicit: each word is a node, and two words are
connected if they differ by one letter. BFS over words finds the shortest
transformation: hit → hot → dot → dog → cog.
ladder_length.py — LC 127python
from collections import deque
def ladder_length(begin_word, end_word, word_list):
"""Find shortest transformation sequence length."""
word_set = set(word_list)
if end_word not in word_set:
return 0
queue = deque([(begin_word, 1)]) # (word, steps)
visited = {begin_word}
while queue:
word, steps = queue.popleft()
# Try changing each character to a-z
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = word[:i] + c + word[i+1:]
if next_word == end_word:
return steps + 1
if next_word in word_set and next_word not in visited:
visited.add(next_word)
queue.append((next_word, steps + 1))
return 0 # no transformation sequence existsP5Open the Lock (LC 752) — state-space BFS
The state is the full 4-digit combination like "0132";
edges connect combinations one wheel-turn apart. Each turn costs 1 step, so BFS
finds the minimum number of turns. The visited set must track full states,
not single digits.
open_lock.py — LC 752python
from collections import deque
def open_lock(deadends, target):
"""Minimum turns to reach target from '0000'. State-space BFS."""
dead = set(deadends)
if '0000' in dead:
return -1
queue = deque([('0000', 0)])
visited = {'0000'}
while queue:
state, turns = queue.popleft()
if state == target:
return turns
# Try turning each of 4 wheels up or down
for i in range(4):
digit = int(state[i])
for delta in [1, -1]:
new_digit = (digit + delta) % 10
new_state = state[:i] + str(new_digit) + state[i+1:]
if new_state not in visited and new_state not in dead:
visited.add(new_state)
queue.append((new_state, turns + 1))
return -106 complexity
Complexity reference
| Problem | Time | Space | Notes |
|---|---|---|---|
| Tree BFS | O(n) | O(w) | w = max width, up to n/2 |
| Graph BFS | O(V + E) | O(V) | V vertices, E edges |
| Grid BFS | O(R · C) | O(R · C) | R rows, C cols |
| Multi-source BFS | O(R · C) | O(R · C) | Same as single-source |
| Word Ladder | O(M² · N) | O(M · N) | M = word length, N = word count |
| Open the Lock | O(10⁴ · 4) | O(10⁴) | 10000 states, 8 edges each |
| Shortest Path Binary Matrix | O(n²) | O(n²) | n × n grid |
Space: BFS vs. DFS
For a balanced binary tree with n nodes:
BFS space: O(n/2) = O(n) (widest level has ~n/2 nodes)
DFS space: O(log n) (height of balanced tree)
For a skewed tree (linked list shape):
BFS space: O(1) (each level has 1 node)
DFS space: O(n) (height = n)
Summary: BFS uses more memory on wide graphs,
DFS uses more memory on deep graphs.
07 common mistakes
Where BFS goes wrong
Mistake 1 — marking visited when processing, not when enqueuing
The most common BFS bug. If you mark on pop, a node can be enqueued
multiple times before its first pop — duplicate work at best, exponential blowup at worst.
the fixpython
# WRONG: mark when processing (node may be enqueued multiple times)
while queue:
node = queue.popleft()
visited.add(node) # TOO LATE -- duplicates already in queue
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
# RIGHT: mark when enqueuing
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor) # mark IMMEDIATELY
queue.append(neighbor)Mistake 2 — forgetting to track levels
If you need level information, you must snapshot and process exactly
len(queue) nodes per iteration of the outer loop.
Mistake 3 — using a list as a queue
list.pop(0) is O(n) — it shifts every remaining element.
Always use collections.deque with popleft().
Mistake 4 — not handling disconnected graphs
BFS from one start node won't reach disconnected components. Loop through all
nodes and start a BFS from each unvisited one if needed.
Mistake 5 — multi-source: adding sources one at a time
All sources must be in the queue before BFS starts. Otherwise you get
single-source distances instead of nearest-source distances.
Mistake 6 — BFS on a weighted graph
The shortest-path guarantee only holds when every edge costs the same.
Weighted graphs need Dijkstra; 0/1 weights allow 0-1 BFS with a deque.
Mistake 7 — state-space: defining state too small
For Open the Lock, the state is the full combination "0132", not one
digit. The visited set must track complete states or you'll revisit endlessly.
Mistake 8 — infinite loop on grids
Always mark cells visited (or mutate their value in place) the moment you
enqueue them, or the wavefront washes back over itself forever.
10 practice
Practice ladder
In this order — easiest first. Tick each one as you solve it, and re-solve anything that took more than 25 minutes two days later.
16 problems