A queue, a visited set, and one loop that processes a whole level at a time. The first time BFS reaches a node, it has reached it by the shortest route.
BFS is the answer to two very different questions that turn out to be the same question: process this tree level by level, and find the fewest steps from A to B. Both fall out of the same property, that a queue explores in order of distance from the start.
| Signal | What it looks like |
|---|---|
| Level language | “level order”, “by depth”, “the rightmost node of each row”, “average per level”. |
| Shortest-path language | “minimum number of moves”, “fewest transformations”, “how many minutes until…”. |
| Spreading | Infection, fire, water, rot. Anything expanding outward one unit of time at a time. |
| Nearest something | “distance to the closest zero”, “nearest exit”. Often a multi-source BFS. |
| BFS | DFS | |
|---|---|---|
| Best at | Shortest path, level structure | All paths, connectivity, bottom-up values |
| Data structure | Queue, explicit | Stack, usually the call stack |
| Memory | O(width) — can be huge on a wide tree | O(depth) — can be huge on a deep one |
| Finds the shortest path? | Yes, on unweighted graphs | No, not without extra work |
d is dequeued before any node at distance d + 1. So the first time a node is reached, it is reached along a shortest path, and it never needs revisiting.size = len(queue) before the inner loop and pop exactly that many. Everything pushed during the inner loop belongs to the next level and is left for the next round. This one line is the difference between a flat traversal and a level-grouped one.# One outer pass per level. Invariant: at the top, the queue holds exactly
# one whole level and nothing else.
while queue:
size = len(queue) # snapshot BEFORE the inner loop
for _ in range(size): # pop exactly `size` nodes: this level only
node = queue.popleft() # popleft: oldest first, so FIFO order
# ... push children. They land after the snapshot boundary.
for _ in range(len(queue)) if the queue is mutated and you re-read it. Python evaluates range(len(queue)) once, so that form is actually safe and is the idiomatic one-liner. The bug is writing while len(queue) > 0 as the inner loop, which never terminates because children keep arriving.from dataclasses import dataclass
@dataclass
class TreeNode:
"""A binary tree node."""
val: int = 0 # 0: default payload when none is given
# Quoted types: TreeNode is not fully defined yet on these lines.
left: "TreeNode | None" = None # None: no left child
right: "TreeNode | None" = None # None: no right child
from collections import deque
def by_level(root: TreeNode | None) -> list[list[int]]:
"""Group a tree's values by depth."""
if root is None:
return [] # empty tree: no levels at all
levels: list[list[int]] = []
queue = deque([root]) # level 0 is just the root
# Invariant: at the top of each pass, the queue holds one whole level.
while queue:
level: list[int] = []
for _ in range(len(queue)): # exactly this level's nodes
node = queue.popleft() # popleft: oldest first (FIFO)
level.append(node.val)
# Children go to the back. They form the next level.
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
levels.append(level)
return levels
A tree needs no visited set, because there is exactly one path to every node. A graph always does.
def shortest_steps(start, goal, neighbours) -> int:
"""Fewest edges from start to goal, or -1 if unreachable."""
queue = deque([start])
seen = {start} # start is reached before any step
steps = 0 # 0: start is 0 edges from itself
# Invariant: the queue holds every node exactly `steps` edges from start.
while queue:
for _ in range(len(queue)): # len(queue): just this distance ring
node = queue.popleft()
# BFS reaches nodes in distance order, so the first hit is shortest.
if node == goal:
return steps
for nxt in neighbours(node):
if nxt not in seen:
seen.add(nxt) # mark on PUSH, not on pop
queue.append(nxt)
steps += 1 # + 1: the next ring is one edge farther
return -1 # -1: queue ran dry, goal not reachable
Reading the figure. Numbers are the step count from S. Blue cells were popped in earlier rounds. Amber cells are in the queue now. Green is the goal. Notice that the queue holds only one ring. Every cell at distance 3 leaves the queue before any cell at distance 4 is seen.
list.pop(0) is O(n), which makes the whole BFS O(n²). Always collections.deque.0, and a poorly placed goal test returns 1.Return the values of a binary tree grouped by level, from left to right, top to bottom.
from collections import deque
def level_order(root: TreeNode | None) -> list[list[int]]:
"""Values of a binary tree, grouped by depth.
Args:
root: Root node, or None.
Returns:
One list per level, top to bottom, each left to right.
Example:
Tree 3 / (9, 20) / (None, None, 15, 7) gives [[3], [9, 20], [15, 7]]
"""
if root is None:
return [] # empty tree: no levels at all
levels: list[list[int]] = []
queue = deque([root]) # level 0 is just the root
# Invariant: at the top of each pass, the queue holds one whole level.
while queue:
level: list[int] = []
# len(queue) here is exactly the width of the current level.
for _ in range(len(queue)):
node = queue.popleft() # popleft: oldest first (FIFO)
level.append(node.val)
# Left before right keeps each level in left-to-right order.
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
levels.append(level)
return levels
Reading the figure. Amber boxes are the queue when a round starts. That count is size. Blue boxes are the children pushed during the round, which are the next level. Green text is the list the round adds to levels. Each blue row becomes the next amber row.
Each node is enqueued and dequeued exactly once. The queue holds at most one level plus part of the next, so its peak is the maximum width, which is O(n) in the worst case and roughly n/2 for a full tree.
| Question | Change to the template |
|---|---|
| Bottom-up level order | Build normally, then levels.reverse(), or appendleft into a deque. |
| Right side view | Append only the last value of each level. |
| Average of each level | sum(level) / len(level) instead of the list. |
| Maximum depth | Count the rounds of the outer loop. |
| Minimum depth | Return the round number at the first leaf you dequeue. |
Five interview questions, one loop. This is why the template is worth memorising exactly.
root is None: returns [], not [[]].[[val]].n levels of one node each, and the queue never exceeds size 1.Same as above, but alternate direction: the first level left to right, the second right to left, and so on.
deque with appendleft does this in O(1) per node, so no reversal pass is needed.from collections import deque
def zigzag_level_order(root: TreeNode | None) -> list[list[int]]:
"""Level order, alternating left-to-right and right-to-left.
Args:
root: Root node, or None.
Returns:
One list per level, with odd-numbered levels reversed.
Example:
[[3], [20, 9], [15, 7]]
"""
if root is None:
return [] # empty tree: no levels at all
levels: list[list[int]] = []
queue = deque([root]) # level 0 is just the root
left_to_right = True # level 0 reads left to right
# Invariant: at the top of each pass, the queue holds one whole level,
# and left_to_right says which way to write it.
while queue:
# A deque lets us write to either end in O(1), so no reversal pass.
level: deque[int] = deque()
for _ in range(len(queue)): # len(queue): this level's nodes only
node = queue.popleft()
if left_to_right:
level.append(node.val) # back: keeps the visit order
else:
level.appendleft(node.val) # front: reverses the visit order
# The queue itself always goes left then right. Only `level` flips.
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
levels.append(list(level))
left_to_right = not left_to_right # flip direction for the next level
return levels
appendleft.Reading the figure. Purple arrows show the direction each level is written. The amber level is the one that reads right to left. The boxes on the right are its level deque. BFS still pops 9 before 20. appendleft puts 20 in front, so the level reads [20, 9] with no extra pass.
right before left on alternating levels. That produces the right answer on a perfect tree and the wrong one as soon as a node has only one child, because the mirrored ordering no longer lines up level to level. Keep the traversal canonical and change only the output order. Interviewers ask this exact follow-up.list(level) copies, but each node is copied once overall, so it does not change the bound. Using level.reverse() on a plain list would also be O(n) total; the deque version just avoids the second touch.
A grid holds 0 for empty, 1 for a fresh orange, 2 for a rotten one. Every minute, a rotten orange rots each fresh orange directly adjacent to it, in the four cardinal directions. Return the number of minutes until no fresh orange remains, or -1 if that never happens.
-1 case at the end, with no second scan of the grid.from collections import deque
# Down, up, right, left as (row step, col step). No diagonals.
DIRECTIONS: tuple[tuple[int, int], ...] = ((1, 0), (-1, 0), (0, 1), (0, -1))
def oranges_rotting(grid: list[list[int]]) -> int:
"""Minutes until every fresh orange rots, or -1 if some never do.
Args:
grid: 0 empty, 1 fresh, 2 rotten. Mutated in place as rot spreads.
Returns:
Elapsed minutes, or -1 if at least one fresh orange is unreachable.
Example:
>>> oranges_rotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]])
4
"""
# grid[0]: the first row. If it is empty, there are no columns.
if not grid or not grid[0]:
return 0 # 0: no oranges, so no time passes
rows, cols = len(grid), len(grid[0]) # grid[0]: every row has this width
queue: deque[tuple[int, int]] = deque()
fresh = 0 # 0: count starts empty
# Seed every rotten cell at once: this is a multi-source BFS.
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2: # 2: rotten, a starting source
queue.append((r, c))
elif grid[r][c] == 1: # 1: fresh, must rot before we finish
fresh += 1 # + 1: one more fresh orange to rot
if fresh == 0:
return 0 # nothing to rot, even if the grid is empty
minutes = 0 # 0: time starts before any spread
# Stop as soon as nothing fresh is left, so we do not count a final
# empty round.
# Invariant: the queue holds exactly the cells that rotted at `minutes`.
while queue and fresh > 0:
for _ in range(len(queue)): # len(queue): one minute's wave only
r, c = queue.popleft()
for dr, dc in DIRECTIONS:
nr, nc = r + dr, c + dc
# 0 <= ... < rows/cols: stay on the grid. == 1: fresh only.
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2 # mark on push: the grid is the visited set
fresh -= 1 # - 1: one fewer fresh orange left
queue.append((nr, nc))
minutes += 1 # + 1: one wave of spread is one minute
# fresh == 0: all rotted. Otherwise -1: some orange was walled off.
return minutes if fresh == 0 else -1
[[2,1,1],[1,1,0],[0,1,1]], one rotten orange at the top left and six fresh:
| minute | newly rotten | fresh left |
|---|---|---|
| 1 | (0,1) and (1,0) | 4 |
| 2 | (0,2) and (1,1) | 2 |
| 3 | (2,1) | 1 |
| 4 | (2,2) | 0 |
Answer 4.
Reading the figure. Amber cells are the queue for that minute, the oranges that just turned rotten. Blue cells rotted in an earlier minute. White cells are still fresh. Grey cells are empty. Read left to right. Each amber set touches the one before it, and the count under each grid drops to 0 at minute 4.
Every cell is enqueued at most once. The queue peaks at the size of the rot frontier, which is O(rows × cols) in the worst case.
while queue and fresh > 0while queue, the last round dequeues the final frontier, finds no fresh neighbours, and still increments minutes. That over-counts by one. Adding fresh > 0 stops as soon as the job is finished. The alternative fix is to increment only when something actually rotted; both are fine, but pick one and explain it.0, including for an all-zero grid.fresh > 0, returns -1.-1.Given begin_word, end_word, and a dictionary word_list, find the length of the shortest transformation sequence from begin_word to end_word, where each step changes exactly one letter and every intermediate word must be in the dictionary. The length counts words, not steps. Return 0 if there is no such sequence.
| Method | Cost per word | When it wins |
|---|---|---|
| Compare against every other word | O(N · L) | Never, in an interview. Mention and discard. |
| Try all 26 letters at each of L positions | O(26 · L²) with slicing | The dictionary is large relative to the word length. This is the standard answer. |
Pre-build wildcard buckets like h*t | O(L) lookups after O(N · L²) setup | Many queries against one dictionary. |
With N words of length L: the second option gives O(N · 26 · L²) overall, since building each candidate string by slicing is itself O(L).
import string
from collections import deque
def ladder_length(begin_word: str, end_word: str, word_list: list[str]) -> int:
"""Length of the shortest one-letter-at-a-time word ladder.
Args:
begin_word: Starting word. Need not be in word_list.
end_word: Target word. Must be in word_list or the answer is 0.
word_list: The permitted intermediate words.
Returns:
Number of words in the shortest ladder, counting both ends, or 0.
Example:
>>> ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])
5
"""
words = set(word_list) # O(1) membership, and it is our visited set
if end_word not in words:
return 0 # 0: no ladder can end on a banned word
queue: deque[str] = deque([begin_word])
words.discard(begin_word) # discard, not remove: it may not be listed
steps = 1 # the ladder includes begin_word itself
# Invariant: the queue holds every word that is `steps` words into a ladder.
while queue:
for _ in range(len(queue)): # len(queue): this ladder length only
word = queue.popleft()
# BFS finds words in ladder-length order, so the first hit is shortest.
if word == end_word:
return steps
# Neighbours: change one letter at a time, in every position.
for i in range(len(word)): # i: the position being changed
# i + 1: the suffix skips the letter at i, which we replace.
prefix, suffix = word[:i], word[i + 1 :]
for letter in string.ascii_lowercase: # try all 26 letters
candidate = prefix + letter + suffix
if candidate in words:
words.remove(candidate) # mark on push
queue.append(candidate)
steps += 1 # + 1: the next ring adds one word
return 0 # 0: queue ran dry, no ladder exists
words is the visited set. A word that has been reached at distance d can never be usefully reached again, because any later route to it is at least as long. Deleting it does double duty: it prevents revisits and it shrinks the candidate set as the search proceeds. This is why no separate seen structure appears.begin = "hit", end = "cog", dictionary ["hot","dot","dog","lot","log","cog"]:
| steps | frontier |
|---|---|
| 1 | hit |
| 2 | hot |
| 3 | dot, lot |
| 4 | dog, log |
| 5 | cog → match, return 5 |
cog is found at the fewest steps.Reading the figure. Each column is one round of BFS, and the label on top is the value of steps. Lines join words that differ by one letter. Green boxes and lines trace one shortest ladder. Blue boxes are reached but not on it. Dashed lines join two words in the same round. BFS never uses them, because the far word is already removed from words.
# Sketch, not full code. Search from both ends and always expand the
# smaller frontier. If the branching factor is b and the answer is at
# depth d, this visits about 2 * b**(d/2) nodes instead of b**d.
# 2 *: two searches. d/2: each only goes half the depth.
front, back = {begin_word}, {end_word}
# Invariant: front and back are the current frontiers, and they do not touch yet.
while front and back:
if len(front) > len(back):
front, back = back, front # always expand the cheaper side
# ... expand `front` one level. If it touches `back`, the two halves meet.
On a real dictionary this is often several times faster. Mentioning it, with the b**(d/2) argument, is a strong finish to this question.
end_word not in the dictionary: return 0 immediately. This check is required, not an optimisation.begin_word == end_word: returns 1 on the first pop. Confirm that is the expected answer.begin_word may or may not be in the dictionary. discard rather than remove, so a missing key is not an error.0.collections.deque, never a list. list.pop(0) is O(n).len(queue) at the top of the round. That is what separates one level from the next.Pattern 8, Depth-First Search, is the other traversal. It cannot find shortest paths, but it can do what BFS finds awkward: enumerate every path, compute a value bottom-up from the leaves, and flood-fill a connected region.