35 questions using this pattern
Level-by-level traversal using a queue, exploring all neighbors at the current depth before moving deeper. This guarantees the shortest path in unweighted graphs and is ideal for problems requiring layer-by-layer processing.
Imagine dropping a stone into a still pond. Ripples spread outward in concentric circles—first touching everything 1 meter away, then 2 meters, then 3 meters. BFS works the same way: it explores all nodes at distance 1 before any node at distance 2.
Another analogy: searching for someone in a building. You check everyone on your current floor before taking the stairs to the next floor. You never go upstairs until you've searched every room on the current level.
BFS uses a queue (FIFO) to process nodes in the order they were discovered. This guarantees that when you first reach a node, you've taken the shortest path to get there (in terms of number of edges).
The key insight is that the queue naturally separates nodes by their distance from the source. Everything added in round 1 is at distance 1. Everything added in round 2 is at distance 2. By the time you dequeue a node, all closer nodes have already been processed.
Why it finds shortest paths: If there were a shorter path to node X, you would have discovered X earlier (through that shorter path) and already processed it. The first time you reach X is always via the shortest route.
def bfs(root): if not root: return [] result = [] queue = [root] while queue: # Dequeue front node node = queue.pop(0) result.append(node.val) # Enqueue children (left first, then right) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return resultWe have a binary tree. Our goal is to visit all nodes level by level, from left to right at each level.
Example: Shortest path from A to F
Graph:
A --- B --- E
| |
C --- D --- F
BFS from A:
Queue: [A] Visited: {A} Level 0
Process A → add B, C
Queue: [B, C] Visited: {A,B,C} Level 1
Process B → add E, D
Process C → add D (skip, visited)
Queue: [E, D] Visited: {A,B,C,E,D} Level 2
Process E → no new neighbors
Process D → add F
Queue: [F] Visited: {A,B,C,E,D,F} Level 3
Process F → Found! Distance = 3
Level-order tree traversal:
1
/ \
2 3
/ \ \
4 5 6
Level 0: [1]
Level 1: [2, 3]
Level 2: [4, 5, 6]
Result: [[1], [2,3], [4,5,6]]
Use this skeleton as a starting point for problems using this pattern:
from collections import deque
def bfs_shortest_path(graph: dict, start: str, end: str) -> int:
"""Find shortest path distance in unweighted graph."""
if start == end:
return 0
queue = deque([start])
visited = {start}
distance = 0
while queue:
distance += 1
# Process all nodes at current level
for _ in range(len(queue)):
node = queue.popleft()
for neighbor in graph[node]:
if neighbor == end:
return distance
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return -1 # No path found
def bfs_level_order(root) -> list[list]:
"""Level-order traversal of binary tree."""
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
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
def bfs_matrix(grid: list[list[int]], start: tuple) -> int:
"""BFS on a 2D grid."""
rows, cols = len(grid), len(grid[0])
queue = deque([start])
visited = {start}
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
distance = 0
while queue:
for _ in range(len(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 (nr, nc) not in visited
and grid[nr][nc] != 0): # 0 = wall
visited.add((nr, nc))
queue.append((nr, nc))
distance += 1
return distanceLook for these keywords and patterns in problem descriptions:
Marking nodes as visited when you dequeue them (instead of when you enqueue them) causes the same node to be added multiple times, leading to incorrect distances and wasted processing.
Fix:
Always mark nodes as visited immediately when adding to the queue:
if neighbor not in visited:
visited.add(neighbor) # Mark NOW
queue.append(neighbor)
Processing the entire queue without tracking level boundaries makes it impossible to know the distance or handle level-by-level logic.
Fix:
Use the "process current level size" pattern:
for _ in range(len(queue)): # Fixed size at level start
node = queue.popleft()
# Process node
distance += 1 # Increment after level completes
Classic BFS to find minimum number of edges between two nodes.
Examples: Word Ladder, Minimum Genetic Mutation, Open the Lock
Process tree nodes level by level, returning grouped results.
Examples: Binary Tree Level Order Traversal, Zigzag Level Order
Start BFS from multiple sources simultaneously. Useful for "spreading" problems where multiple starting points expand in parallel.
Examples: Rotting Oranges, Walls and Gates, 01 Matrix
Search from both start and end simultaneously, meeting in the middle. Reduces search space from O(b^d) to O(b^(d/2)).
Examples: Word Ladder (optimized), Shortest Path in large graphs
Track additional state beyond position (e.g., keys collected, walls broken). State becomes part of the "node" being visited.
Examples: Shortest Path in Grid with Obstacles Elimination
Start here to build foundational understanding.
Master the pattern with these representative problems.
Test your mastery with complex variations.
Explore similar techniques:
Navigate 2D grids systematically using DFS, BFS, or directional iteration. Matrix traversal combines graph traversal concepts with coordinate-based movement, treating each cell as a node connected to its neighbors.
Explore as deep as possible along each branch before backtracking, using recursion or an explicit stack. DFS is memory-efficient and naturally suited for problems involving paths, connectivity, and exhaustive exploration.
Visit all nodes in a binary tree in specific orders: preorder (root-left-right), inorder (left-root-right), postorder (left-right-root), or level-order (BFS). Each order reveals different structural information about the tree.
Using list.pop(0) is O(n) because all elements must shift. This turns
O(V+E) BFS into O(V²).
Fix:
Use collections.deque which has O(1) popleft:
from collections import deque
queue = deque([start])
Moving to invalid coordinates (negative or beyond grid dimensions) causes index errors.
Fix:
Always validate coordinates before accessing the grid:
if 0 <= nr < rows and 0 <= nc < cols:
# Safe to access grid[nr][nc]