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.while queue:
size = len(queue) # snapshot BEFORE the inner loop
for _ in range(size):
node = queue.popleft()
# ... 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
left: "TreeNode | None" = None
right: "TreeNode | None" = None
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 []
levels: list[list[int]] = []
queue = deque([root])
while queue:
level: list[int] = []
for _ in range(len(queue)): # exactly this level's nodes
node = queue.popleft()
level.append(node.val)
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}
steps = 0
while queue:
for _ in range(len(queue)):
node = queue.popleft()
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
return -1
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 []
levels: list[list[int]] = []
queue = deque([root])
while queue:
level: list[int] = []
# len(queue) here is exactly the width of the current level.
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
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
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 []
levels: list[list[int]] = []
queue = deque([root])
left_to_right = True
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)):
node = queue.popleft()
if left_to_right:
level.append(node.val)
else:
level.appendleft(node.val)
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
return levels
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
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
"""
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
queue: deque[tuple[int, int]] = deque()
fresh = 0
# 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:
queue.append((r, c))
elif grid[r][c] == 1:
fresh += 1
if fresh == 0:
return 0 # nothing to rot, even if the grid is empty
minutes = 0
# Stop as soon as nothing fresh is left, so we do not count a final
# empty round.
while queue and fresh > 0:
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 grid[nr][nc] == 1:
grid[nr][nc] = 2 # mark on push: the grid is the visited set
fresh -= 1
queue.append((nr, nc))
minutes += 1
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.
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
queue: deque[str] = deque([begin_word])
words.discard(begin_word)
steps = 1 # the ladder includes begin_word itself
while queue:
for _ in range(len(queue)):
word = queue.popleft()
if word == end_word:
return steps
# Neighbours: change one letter at a time, in every position.
for i in range(len(word)):
prefix, suffix = word[:i], word[i + 1 :]
for letter in string.ascii_lowercase:
candidate = prefix + letter + suffix
if candidate in words:
words.remove(candidate) # mark on push
queue.append(candidate)
steps += 1
return 0
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 |
# 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.
front, back = {begin_word}, {end_word}
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.