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
left: "TreeNode | None" = None
right: "TreeNode | None" = None
class GraphNode:
"""An undirected graph node with an adjacency list."""
def __init__(self, val: int = 0, neighbors: list["GraphNode"] | None = None):
self.val = val
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:
return 0 # the base case defines the whole recursion
left = summarise(node.left)
right = summarise(node.right)
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] = []
def walk(node: TreeNode | None) -> None:
if node is None:
return
trail.append(node.val) # choose
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.
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])
stack = [(r, c)]
grid[r][c] = "0" # mark on push
while stack:
row, col = stack.pop()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = row + dr, col + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
grid[nr][nc] = "0"
stack.append((nr, nc))
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
return 1 + max(max_depth(root.left), max_depth(root.right))
def max_depth_iterative(root: TreeNode | None) -> int:
"""Same answer with an explicit stack of (node, depth) pairs."""
if root is None:
return 0
best = 0
stack: list[tuple[TreeNode, int]] = [(root, 1)]
while stack:
node, depth = stack.pop()
best = max(best, depth)
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] = []
def walk(node: TreeNode | None, remaining: int) -> None:
if node is None:
return
trail.append(node.val) # choose
remaining -= node.val
if node.left is None and node.right is None:
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)
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.
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.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
"""
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
islands = 0
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"
while stack:
r, c = stack.pop()
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] = "0" # mark on push
stack.append((nr, nc))
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
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.
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."""
if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != "1":
return
grid[r][c] = "0"
for dr, dc in DIRECTIONS:
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
clones: dict[GraphNode, GraphNode] = {}
def copy(original: GraphNode) -> GraphNode:
existing = clones.get(original)
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
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
clones = {node: GraphNode(node.val)}
queue = deque([node])
while queue:
original = queue.popleft()
for neighbour in original.neighbors:
if neighbour not in clones:
clones[neighbour] = GraphNode(neighbour.val)
queue.append(neighbour)
clones[original].neighbors.append(clones[neighbour])
return clones[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.
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.