Follow one path to the end, then unwind and try the next. The call stack keeps the path for you, which is why DFS code is so much shorter than the problem sounds.
BFS answers “how far”. DFS answers “which paths” and “what is true of this whole subtree”. It is the workhorse of tree questions, because most tree questions are naturally recursive: the answer for a node is some combination of the answers for its children.
| Signal | What it looks like |
|---|---|
| Path language | “all root-to-leaf paths”, “does a path exist”, “path sum”. |
| Subtree language | “height”, “is it balanced”, “diameter”, “is it a valid BST”, “lowest common ancestor”. |
| Region language | “connected components”, “count the islands”, “flood fill”, “surrounded regions”. |
| Structure copying | “clone this graph”, “serialise and deserialise”, “deep copy with random pointers”. |
| Ordering | Topological sort, cycle detection in a directed graph. |
Almost every DFS question is one of these three. Naming the shape before you write is the fastest way to get the code right.
| Shape | What it does | Examples |
|---|---|---|
| Bottom-up (return a value) | Each call returns a summary of its subtree; the parent combines the children’s returns. | Maximum depth, is-balanced, diameter, count nodes. |
| Top-down (pass state in) | Each call carries context from the root down, and records a result at the leaves. | Path sum, all root-to-leaf paths, valid BST with bounds. |
| Mark and spread | No return value. Visit, mark, recurse into unmarked neighbours. | Number of islands, flood fill, connected components. |
from dataclasses import dataclass, field
@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
class GraphNode:
"""An undirected graph node with an adjacency list."""
# val=0: default payload. neighbors=None, not []: a [] default would be
# one shared list across every node.
def __init__(self, val: int = 0, neighbors: list["GraphNode"] | None = None):
self.val = val
# None means "no list given", so build a fresh empty one for this node.
self.neighbors = neighbors if neighbors is not None else []
def summarise(node: TreeNode | None) -> int:
"""Combine children's answers into this node's answer."""
if node is None:
# 0: the answer for an empty subtree. Max Depth: an empty tree has depth 0.
return 0 # the base case defines the whole recursion
# Trust the calls: each returns the full answer for its subtree.
left = summarise(node.left)
right = summarise(node.right)
# combine(val, left, right): build this node's answer from its children's.
# Max Depth: 1 + max(left, right), one for this node plus the deeper side.
return combine(node.val, left, right)
def collect(root: TreeNode | None) -> list[list[int]]:
"""Record every root-to-leaf path that qualifies."""
results: list[list[int]] = []
trail: list[int] = [] # values from the root down to the current node
# Invariant: on entry and on exit, trail is the path to node's parent.
def walk(node: TreeNode | None) -> None:
if node is None:
return # past a leaf: nothing to record
trail.append(node.val) # choose
# qualifies(trail): does this full path count?
# Path Sum II: sum(trail) == target_sum.
# Both children None means a leaf, so trail is a full root-to-leaf path.
if node.left is None and node.right is None and qualifies(trail):
results.append(list(trail)) # COPY, the trail keeps changing
else:
walk(node.left)
walk(node.right)
trail.pop() # un-choose: this is the backtrack
walk(root)
return results
Choose, recurse, un-choose. Every top-down DFS with a shared mutable trail has this shape, and it is the same shape as backtracking.
Reading the figure. Each column is the trail list after one step, with the root at the bottom. Amber is a value just pushed. Green is a push that reached a leaf, where a copy is recorded. Blue values are lower on the path. Red labels mark the un-choose step. Notice that the trail grows and shrinks like the call stack in Figure 8.1, and ends empty.
def flood(grid: list[list[str]], r: int, c: int) -> None:
"""Mark the whole connected region containing (r, c). No recursion depth risk."""
rows, cols = len(grid), len(grid[0]) # grid[0]: every row has this width
stack = [(r, c)]
grid[r][c] = "0" # mark on push
# Invariant: every cell on the stack is land already marked "0".
while stack:
row, col = stack.pop() # pop from the end: LIFO, so depth-first
# Down, up, right, left as (row step, col step). No diagonals.
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = row + dr, col + dc
# 0 <= ... < rows/cols: stay on the grid. "1": unvisited land only.
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
grid[nr][nc] = "0" # "0": sink it so no one pushes it again
stack.append((nr, nc))
Reading the figure. Violet cells are land not reached yet. Amber cells are on the stack, and they already read "0" because marking happens on push. Red cells were popped and are done. Grey cells are water. Notice that (0,0) is never pushed again when (0,1) looks back at it.
results.append(trail) stores a reference to a list that keeps mutating, so every result ends up identical and usually empty. Use list(trail) or trail[:].pop(), the trail grows forever and every path after the first is wrong.0 where it should be -inf, or True where it should be False.Return the number of nodes along the longest path from the root down to the furthest leaf.
0, so a leaf gets 1 + max(0, 0) = 1. Correct without any special leaf handling.def max_depth(root: TreeNode | None) -> int:
"""Number of nodes on the longest root-to-leaf path.
Args:
root: Root node, or None.
Returns:
0 for an empty tree, 1 for a single node, and so on.
"""
if root is None:
return 0 # 0: an empty tree has no nodes on any path
# 1 +: count this node, then add the deeper of the two subtrees.
return 1 + max(max_depth(root.left), max_depth(root.right))
Reading the figure. This uses the tree 3, 9, 20, 15, 7 from the BFS page. Blue nodes have finished and returned the purple number. Purple arrows show a child’s answer flowing up to its parent. The green root holds the final answer. The deeper side, through 20, decides the result.
def max_depth_iterative(root: TreeNode | None) -> int:
"""Same answer with an explicit stack of (node, depth) pairs."""
if root is None:
return 0 # 0: an empty tree has depth 0
best = 0 # 0: no depth seen yet
# 1: the root alone is a path of one node.
stack: list[tuple[TreeNode, int]] = [(root, 1)]
# Invariant: best is the deepest depth among nodes popped so far, and
# every node on the stack carries its own correct depth.
while stack:
node, depth = stack.pop()
best = max(best, depth)
# depth + 1: a child sits one level below its parent.
if node.left is not None:
stack.append((node.left, depth + 1))
if node.right is not None:
stack.append((node.right, depth + 1))
return best
Space is O(log n) on a balanced tree and O(n) on a degenerate one. Saying that, rather than just “O(h)”, shows you know what h can be.
| Question | Change |
|---|---|
| Minimum depth | min, but a node with one None child is not a leaf, so it must be special-cased. Classic trap. |
| Is the tree balanced | Return the height, and propagate a sentinel such as -1 upward the moment a subtree is unbalanced. |
| Diameter | Return the height, and update a nonlocal best with left + right at each node. |
| Count nodes | 1 + count(left) + count(right). |
0.1.Return every root-to-leaf path whose node values sum to target_sum. Each path is the list of values along it.
trail list, mutated on the way down and restored on the way back up. That is O(h) space rather than a fresh list per branch.pop() on the way out, on every path through the function.def path_sum(root: TreeNode | None, target_sum: int) -> list[list[int]]:
"""All root-to-leaf paths whose values sum to target_sum.
Args:
root: Root node, or None.
target_sum: The required total. Values may be negative.
Returns:
A list of paths, each a list of values from root to leaf.
Example:
Tree 5 / (4, 8) ... with target 22 gives [[5, 4, 11, 2], [5, 8, 4, 5]]
"""
paths: list[list[int]] = []
trail: list[int] = [] # values from the root down to the current node
# remaining: how much the rest of the path still has to add up to.
# Invariant: on entry and on exit, trail is the path to node's parent.
def walk(node: TreeNode | None, remaining: int) -> None:
if node is None:
return # past a leaf: no path here
trail.append(node.val) # choose
remaining -= node.val # this node pays part of the target
# Both children None means a leaf. Only full paths may count.
if node.left is None and node.right is None:
# == 0: the path used up the target exactly.
if remaining == 0:
paths.append(list(trail)) # copy: trail keeps changing
else:
walk(node.left, remaining)
walk(node.right, remaining)
trail.pop() # un-choose, on every exit path
walk(root, target_sum) # the whole target is still owed at the root
return paths
left is None and right is Noneremaining == 0, you will report paths that stop halfway down, which is wrong. And if you recurse into a None child and test there, a single-child node whose partial sum matches gets reported twice, once from each None. Test for a real leaf, explicitly.list(trail) and not trailtrail is one list that is mutated throughout the traversal. Appending it stores a reference, and by the time the function returns every stored reference points at the same, now-empty, list. This is the most common bug in every backtracking problem, not just this one.
Tree with root 5, children 4 and 8, target 22. The recursion drives down 5 → 4 → 11 → 7, which sums to 27, no match, so it pops back to 11 and tries 2, giving 22 and a recorded path. It unwinds all the way to the root, popping each value, then explores the 8 branch.
Reading the figure. Each leaf shows the sum of its root-to-leaf path. Green leaves and edges sum to 22 and are recorded. Red leaves miss the target. The boxes on the right are trail at the first hit. After that leaf, the walk pops values on the way back up, then tries the 8 branch.
Visiting is O(n), but copying a qualifying path costs O(h) each time, and there can be O(n) of them in a pathological tree.
[], even if target_sum is 0. A path needs at least one node.remaining < 0. Ask whether values are all positive before adding that optimisation.A grid of "1" for land and "0" for water. An island is a group of land cells connected horizontally or vertically. Count the islands.
"0" is the visited marker, which keeps extra space at O(1) beyond the stack. If mutation is forbidden, use a visited set of coordinates and say so.# 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 num_islands(grid: list[list[str]]) -> int:
"""Count connected regions of "1" in a grid, using 4-directional adjacency.
Args:
grid: Rows of "1" (land) and "0" (water). Mutated: land is sunk
to "0" as it is visited.
Returns:
The number of islands.
Example:
>>> num_islands([["1", "1", "0"], ["0", "1", "0"], ["0", "0", "1"]])
2
"""
# grid[0]: the first row. If it is empty, there are no columns.
if not grid or not grid[0]:
return 0 # 0: no cells, so no islands
rows, cols = len(grid), len(grid[0]) # grid[0]: every row has this width
islands = 0 # 0: none found yet
def sink(start_r: int, start_c: int) -> None:
"""Flood the region containing (start_r, start_c), iteratively.
An explicit stack avoids Python's recursion limit, which a large
all-land grid would otherwise blow straight through.
"""
stack = [(start_r, start_c)]
grid[start_r][start_c] = "0" # "0": sink on push so it is never pushed twice
# Invariant: every cell on the stack is land already sunk to "0".
while stack:
r, c = stack.pop() # pop from the end: LIFO, so depth-first
for dr, dc in DIRECTIONS:
nr, nc = r + dr, c + dc
# 0 <= ... < rows/cols: stay on the grid. "1": unsunk land only.
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
grid[nr][nc] = "0" # mark on push
stack.append((nr, nc))
# Scan every cell. Invariant: every island touching a scanned cell is
# counted and fully sunk, so no "1" left behind belongs to it.
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1": # "1": land no flood has reached
islands += 1 # a region we have not seen before
sink(r, c)
return islands
On [["1","1","0"],["0","1","0"],["0","0","1"]]: the scan hits (0,0), counts island 1, and sinks (0,0), (0,1), (1,1). The scan continues over now-water cells until (2,2), counts island 2, and sinks it. Answer 2.
Reading the figure. Violet cells are land not visited yet. Amber is the land cell the scan just found, which adds one to the count. Red cells are sunk to "0". Grey cells are water. Between frame 2 and frame 3 the scan passes over the red cells without counting them.
Every cell is examined by the outer scan once and pushed at most once, so the total is linear in the number of cells despite the nested loops.
def sink_recursive(grid, r, c, rows, cols) -> None:
"""Elegant, but the depth equals the region size."""
# Off the grid, or not unvisited land ("1"): stop here.
if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != "1":
return
grid[r][c] = "0" # "0": sink before recursing, or we loop forever
for dr, dc in DIRECTIONS: # spread to all 4 neighbours
sink_recursive(grid, r + dr, c + dc, rows, cols)
RecursionError long before that. Write the recursive version if it is clearer, then say “in production I would make this iterative because the depth is unbounded”. That sentence is worth real points.0.1, and it is the worst case for stack depth.visited: set[tuple[int, int]] instead, at O(rows × cols) extra memory.Given a reference to a node in a connected, undirected graph, return a deep copy of the whole graph. Each node holds a value and a list of neighbours.
This map does three jobs at once: it is the visited set, it is the place partly-built clones live, and it is how a second edge into the same node finds the same clone rather than making a duplicate.
def clone_graph(node: GraphNode | None) -> GraphNode | None:
"""Deep-copy a connected undirected graph reachable from node.
Args:
node: Any node of the graph, or None for an empty graph.
Returns:
The clone corresponding to node, with the whole graph copied.
"""
if node is None:
return None # empty graph: nothing to copy
# original -> its clone. Doubles as the visited set, so cycles stop.
clones: dict[GraphNode, GraphNode] = {}
def copy(original: GraphNode) -> GraphNode:
existing = clones.get(original) # .get returns None if not built yet
if existing is not None:
return existing # already built, or being built right now
duplicate = GraphNode(original.val)
clones[original] = duplicate # REGISTER FIRST, then recurse
# Each neighbour is cloned (or found in clones) and linked in order.
duplicate.neighbors = [copy(neighbour) for neighbour in original.neighbors]
return duplicate
return copy(node)
from collections import deque
def clone_graph_iterative(node: GraphNode | None) -> GraphNode | None:
"""Same result with an explicit queue, so there is no recursion depth limit."""
if node is None:
return None # empty graph: nothing to copy
# original -> its clone. Build the start node's clone up front.
clones = {node: GraphNode(node.val)}
queue = deque([node])
# Invariant: every node in the queue already has a clone in `clones`.
# Its clone's neighbor list is filled in when the node is popped.
while queue:
original = queue.popleft()
for neighbour in original.neighbors:
# First sighting: make its clone now and queue it once.
if neighbour not in clones:
clones[neighbour] = GraphNode(neighbour.val)
queue.append(neighbour)
# Link the clones in the same order as the originals.
clones[original].neighbors.append(clones[neighbour])
return clones[node] # the clone of the start node
A four-node cycle 1 – 2 – 3 – 4 – 1. copy(1) registers clone 1, then recurses to 2, which registers clone 2, then to 3, then to 4. Node 4’s neighbours are 3 and 1; both are already in the map, so both return immediately and the cycle closes without infinite recursion. The recursion then unwinds, filling in each neighbour list.
Reading the figure. Blue nodes are on the call stack, still waiting for their neighbour lists. Amber is the current call, copy(4). The middle column is clones, filled in the order shown. On the right, 4′ is the clone of node 4. Its green links are done. The dashed links are made as the other calls return.
Each node is created once and each edge is traversed once from each side.
node is None: return None.copy finds the node already registered and links the clone to itself. Works because of the register-first ordering.GraphNode uses default identity hashing. A dataclass with eq=True would break it, which is why GraphNode is a plain class here and not a dataclass.Pattern 9, Top K Elements, changes the tool. Instead of a traversal it uses a heap, and the trick is realising you almost never need the data sorted, only its extremes.