Pattern 03 · Trees & Graphs
Depth-First Search
Explore as deep as possible along each branch before backtracking, powered by a stack — the call stack (recursion) or an explicit one. One idea covers tree traversals, graph cycles, island counting, and topological sort.
time O(V + E)space O(h)orders pre · in · postpractice 18 problems
01 core concept
Go deep, then backtrack
DFS commits to one branch until it bottoms out, then backtracks to the most recent fork and takes the next branch. The stack remembers where the forks are.
DFS traversal on a tree:
1
/ \
2 3
/ \ \
4 5 6
Visit order: 1 -> 2 -> 4 -> (backtrack) -> 5 -> (backtrack) -> 3 -> 6
- Explores depth before breadth.
- Memory: O(h) where h = height of the tree / graph depth.
- Naturally recursive — the call stack is the stack.
- Does NOT guarantee shortest path.
step 1 / 8walkthrough — iterative preorder dfs with an explicit stack
stack [1]
result []
The tree above, flattened to its nodes. Push the root onto the stack. Rightmost stack entry = top. Green = visited.
02 three orders
Pre, in, post — when do you process the node?
All three visit every node exactly once. The only difference is when you process the current node relative to its children.
Example tree:
A
/ \
B C
/ \
D E
PreorderRoot, Left, Right
Process before going to children. Visit order: A → B → D → E → C.
Use for copying / serializing a tree, building prefix expressions, and
top-down problems (pass info down to children).
InorderLeft, Root, Right
Process between left and right children. Visit order: D → B → E → A → C.
On a BST this yields the nodes in sorted order — the key to validating a BST or
finding the kth smallest.
PostorderLeft, Right, Root
Process after both children are done. Visit order: D → E → B → C → A.
Use for deleting a tree (children first), computing height/size, evaluating expression trees,
and bottom-up problems (collect info from children).
1
/ \
2 3
/ \
4 5
Preorder: 1, 2, 4, 5, 3 (root first)
Inorder: 4, 2, 5, 1, 3 (left, root, right)
Postorder: 4, 5, 2, 3, 1 (root last)
03 recognition
DFS vs BFS — and when to reach for which
| Criteria | DFS | BFS |
|---|---|---|
| Data structure | Stack / recursion | Queue |
| Memory | O(h) height | O(w) width |
| Shortest path? | NO (in general) | YES (unweighted) |
| Best for | Path finding, exhaustive search, topological sort | Shortest path, levels |
| Deep narrow tree | Memory efficient | Could be wide at levels |
| Wide shallow tree | Fine | Memory efficient |
Rule of thumb
Need shortest path or level info? → BFS.
Need to explore all paths / backtrack? → DFS.
Graph has cycles? → Either, but track visited.
Tree problem? → DFS (usually simpler to write).
Strategy framework
What kind of problem?
|
+--> TREE problem
| |
| +--> Need sorted order from BST? --> Inorder DFS
| +--> Top-down (pass info to children)? --> Preorder DFS
| +--> Bottom-up (collect from children)? --> Postorder DFS
| +--> Need all paths? --> DFS with path tracking
|
+--> GRAPH problem
| |
| +--> Detect cycles? --> DFS with 3-state coloring
| +--> Dependency ordering? --> Topological sort (DFS postorder)
| +--> Connected components? --> DFS from each unvisited node
| +--> Shortest path? --> BFS instead (not DFS)
|
+--> GRID problem
| |
| +--> Count islands/regions? --> DFS from each unvisited cell
| +--> Flood fill? --> DFS or BFS
| +--> Shortest path? --> BFS instead
|
+--> COMBINATORIAL problem
|
+--> Permutations/subsets? --> DFS with backtracking
+--> N-Queens/Sudoku? --> DFS with constraint checking
When NOT to use it
Anything asking for a shortest path or per-level information in an unweighted
graph or grid — DFS finds a path, not the shortest one. Use
BFS (Pattern 04) instead.
04 templates
The templates and the classics
T1Recursive tree DFS — all three orders in one skeleton
tree_dfs.pypython
def dfs(node):
if not node:
return
# --- PREORDER: process here (before children) ---
# print(node.val)
dfs(node.left)
# --- INORDER: process here (between children) ---
# print(node.val)
dfs(node.right)
# --- POSTORDER: process here (after children) ---
# print(node.val)T2Iterative preorder with an explicit stack
dfs_iterative.pypython
def dfs_iterative(root):
"""Iterative preorder DFS using explicit stack."""
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val) # process node
# Push right first so left is processed first (stack is LIFO)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return resultT3Graph DFS with a visited set
dfs_graph.pypython
def dfs_graph(graph, start):
"""DFS on adjacency list graph."""
visited = set()
def dfs(node):
if node in visited:
return
visited.add(node)
# process node here
print(node)
for neighbor in graph[node]:
dfs(neighbor)
dfs(start)Ex 1Max depth of binary tree — postorder
max_depth.py — LC 104python
def max_depth(root):
"""Postorder DFS -- need children's depths to compute parent's depth."""
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return 1 + max(left_depth, right_depth)
# 3 depth calculation:
# / \ leaf 9: max(0,0)+1 = 1
# 9 20 leaf 15: 1, leaf 7: 1
# / \ node 20: max(1,1)+1 = 2
# 15 7 root 3: max(1,2)+1 = 3Ex 2Path sum — preorder, pass info down
path_sum.py — LC 112python
def has_path_sum(root, target_sum):
"""Check if any root-to-leaf path sums to target. Preorder DFS."""
if not root:
return False
# Subtract current value as we go deeper
target_sum -= root.val
# Leaf node check
if not root.left and not root.right:
return target_sum == 0
return (has_path_sum(root.left, target_sum) or
has_path_sum(root.right, target_sum))Ex 3Number of islands — grid DFS
num_islands.py — LC 200python
def num_islands(grid):
"""Count islands in a grid. DFS to mark visited land."""
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
# Boundary check + water/visited check
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0' # mark as visited (sink the land)
# Explore all 4 directions
dfs(r + 1, c) # down
dfs(r - 1, c) # up
dfs(r, c + 1) # right
dfs(r, c - 1) # left
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1 # found new island
dfs(r, c) # sink entire island
return countGrid:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
Step 1: Find grid[0][0] = '1', count=1, start DFS
Mark (0,0)->0, explore neighbors
Mark (0,1)->0, (1,0)->0, (1,1)->0
Island 1 sunk:
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 1 1
Step 2: Scan... find grid[2][2] = '1', count=2
Mark (2,2)->0
Step 3: Find grid[3][3] = '1', count=3
Mark (3,3)->0, (3,4)->0
All sunk. Result: 3 islands.
Ex 4Course schedule — cycle detection with 3 colors
can_finish.py — LC 207python
def can_finish(num_courses, prerequisites):
"""Detect if course schedule has cycles. 3-state DFS."""
graph = [[] for _ in range(num_courses)]
for course, prereq in prerequisites:
graph[prereq].append(course)
# States: 0 = unvisited, 1 = in progress (on current path), 2 = done
state = [0] * num_courses
def has_cycle(node):
if state[node] == 1: # back edge -> CYCLE
return True
if state[node] == 2: # already fully processed
return False
state[node] = 1 # mark as in-progress
for neighbor in graph[node]:
if has_cycle(neighbor):
return True
state[node] = 2 # mark as done (all descendants processed)
return False
# Check all nodes (graph may be disconnected)
for i in range(num_courses):
if has_cycle(i):
return False
return TrueWhy 3 states instead of 2?
With just visited/unvisited you can't distinguish D → B where B was already fully
processed (a harmless cross edge) from A → B → C → A where A is still
on the current path (a real cycle). Hitting an IN_PROGRESS node =
cycle (it's an ancestor on the current path). Hitting a DONE node = no cycle.
Ex 5Validate BST — preorder with a range
is_valid_bst.py — LC 98python
def is_valid_bst(root):
"""Validate BST by passing valid range down (preorder)."""
def validate(node, low, high):
if not node:
return True
# Current node must be within (low, high) exclusive
if node.val <= low or node.val >= high:
return False
# Left subtree: all values must be < node.val
# Right subtree: all values must be > node.val
return (validate(node.left, low, node.val) and
validate(node.right, node.val, high))
return validate(root, float('-inf'), float('inf'))
# 5
# / \
# 3 7 validate(5, -inf, inf) -> True
# / \ validate(3, -inf, 5) -> True
# 1 4 validate(7, 5, inf) -> True
# validate(1, -inf, 3) -> True
# validate(4, 3, 5) -> TrueEx 6Lowest common ancestor — postorder
lca.py — LC 236python
def lowest_common_ancestor(root, p, q):
"""Find LCA of two nodes in binary tree. Postorder."""
if not root or root == p or root == q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
# If both sides found something, current node is the LCA
if left and right:
return root
# Otherwise, return whichever side found something
return left if left else right
# 3
# / \
# 5 1 LCA(5, 1) = 3 (found on both sides)
# / \ LCA(5, 4) = 5 (5 is ancestor of 4)
# 6 2
# / \
# 7 4Ex 7Topological sort — reversed DFS postorder
topological_sort.py — LC 210python
def topological_sort(num_nodes, edges):
"""Topological ordering using DFS. Returns order or [] if cycle."""
graph = [[] for _ in range(num_nodes)]
for u, v in edges:
graph[u].append(v)
state = [0] * num_nodes # 0=unvisited, 1=in-progress, 2=done
order = []
def dfs(node):
if state[node] == 1:
return False # cycle detected
if state[node] == 2:
return True
state[node] = 1
for neighbor in graph[node]:
if not dfs(neighbor):
return False
state[node] = 2
order.append(node) # postorder: add AFTER all descendants
return True
for i in range(num_nodes):
if state[i] == 0:
if not dfs(i):
return [] # cycle exists, no valid ordering
return order[::-1] # reverse postorder = topological orderCourse dependencies:
0 --> 1 --> 3
| ^
v |
2 ----------+
step 1 / 10walkthrough — topological sort of the graph above
edges 0→1, 0→2, 1→3, 2→3
order []
Four courses. An edge
u → v means u is a prerequisite of v. Ptr labels track the current DFS path; green = done. Start DFS from node 0.Complexity reference
| Problem | Time | Space | Notes |
|---|---|---|---|
| Tree DFS (any order) | O(n) | O(h) | h = height; O(log n) balanced, O(n) skewed |
| Graph DFS | O(V + E) | O(V) | V = vertices, E = edges |
| Grid DFS (islands) | O(R · C) | O(R · C) | worst-case recursion depth |
| Topological sort | O(V + E) | O(V) | |
| Validate BST | O(n) | O(h) | |
| Lowest Common Ancestor | O(n) | O(h) | |
| Path Sum | O(n) | O(h) |
05 common mistakes
Where DFS goes wrong
Mistake 1 — forgetting the base case
if not node: return is essential. Without it you get
AttributeError: NoneType has no attribute 'left'.
Mistake 2 — no visited set in graph DFS
Trees have no cycles, but graphs might. Without a visited set you get
infinite recursion.
Mistake 3 — 2-state instead of 3-state cycle detection
With just visited/unvisited you cannot distinguish back edges (cycles) from cross edges
(already-processed branches). Use unvisited / in-progress / done.
Mistake 4 — marking without unmarking
For "find all paths" problems you must restore visited cells after exploring — otherwise
later paths are blocked by earlier ones.
the fixpython
grid[r][c] = '0' # mark
dfs(neighbors)
grid[r][c] = '1' # UNMARK (backtrack)Mistake 5 — blowing the recursion limit
Python's default limit is ~1000. For deep graphs/grids, either raise it with
sys.setrecursionlimit() or convert to iterative DFS with an explicit stack.
Mistake 6 — wrong traversal order
Preorder when you needed postorder (or vice versa). Ask: do I need information
from children first (postorder) or do I pass information down
(preorder)?
Mistake 7 — BST validation with wrong bounds
Start with (-inf, +inf), not (None, None). And the comparison must be
strict < / >, not <= / >=.
10 practice
Practice ladder
In this order — easiest first. Tick each one as you solve it, and re-solve anything that took more than 25 minutes two days later.
18 problems
mediumLC 236
Postorder — first node where both sides report a hit.
mediumLC 105
Recursive partition — preorder picks the root, inorder splits.