Depth-First Search
- Trace how a recursion frame stores local state and how returning restores the previous frame
- Design DFS parameters by separating what flows down from parent to child and what flows back up
- Implement the five DFS families: tree recursion, graph components, grid flood fill, cycle detection, and post-order aggregation
- Choose DFS over BFS (or vice versa) based on whether the problem needs depth-first exploration or distance-order processing
DFS explores one branch to its end before trying another. The call stack remembers where to backtrack. The pattern covers trees, graphs, and grids, each with a different strategy for tracking what has been visited.
What DFS Actually Does
DFS chooses one branch, carries context in the current stack frame, and explores until it reaches a base case or a dead end. Then it returns, and the previous frame continues with the next branch. The call stack manages all the bookkeeping: which branches have been tried, what state was active at each decision point, and where to resume after a branch finishes.
Without DFS, exploring all branches of a tree or graph means manually tracking every unfinished branch, every partial result, and every position that still needs work. DFS replaces that manual management with function calls. Each call handles one node. Returning from that call restores the caller's state automatically.
Problem: Given a binary tree, find its maximum depth.
Tree DFS · Maximum Depth
ENTER node 1 (root)
Recursive pattern: get answer from both subtrees, combine, return.
Step 1 of 15
Each call asks its children for their depth, waits for both answers, then reports the larger one plus one. The call stack grows as DFS descends and shrinks as nodes return their results.
How the Recursion Stack Explores
Each recursive call pushes a frame onto the call stack. A frame stores the current node, the function's local variables, and the point in the code where execution will resume after the call returns. When the call finishes, the frame is popped, and the previous frame picks up exactly where it left off.
This is why DFS does not need an explicit data structure to track which branches are still pending. The call stack does it. Each pending branch corresponds to a frame that has called into a child and is waiting for the return value.
The order in which you place work relative to recursive calls determines traversal order. If you process the current node before calling children, that is pre-order. If you process it after both children return, that is post-order. The stack is the same in both cases. The difference is where the "do work" line sits in relation to the recursive calls.
Recursion depth equals the longest path from the root to the deepest node being explored. For balanced trees that is O(log n). For skewed trees (every node has only one child) it is O(n), which can exceed Python's default recursion limit of about 1000 frames.
What Each Frame Is Responsible For
Every recursion frame has three responsibilities. First, it receives context from its parent through parameters. Second, it does local computation at the current node. Third, it either returns a value to its parent or mutates shared state. Designing a DFS solution means deciding what happens in each of these three stages.
What Flows Down
Parameters carry information from parent to child. The type of parameter determines whether you need cleanup after returning from a branch.
Pattern A: Accumulating Parameters (Immutable)
This pattern works well for tracking running totals, depths, or constraints. No cleanup needed because integers are immutable, so each branch gets its own copy.
Because target - node.val creates a new integer, each recursive branch has its own copy. No state sharing, no bugs.
Pattern B: Path Parameters (Mutable)
Track the actual sequence of visited nodes with this pattern. Requires cleanup because lists are shared across branches.
path.copy(), all saved paths point to the same list object. As you continue traversing, that list changes. Every saved path contains incorrect data.Pattern C: Bound Parameters
Use this pattern for validating constraints that narrow at each level.
Pattern D: Parent Parameter
Use in undirected graphs to skip the node you came from.
Pattern E: Depth Parameter
Track how many levels deep you are. Essential for level-based problems like "nodes at distance K" or "rightmost node per level".
What Flows Up
The return type controls what information flows back from child to parent. There are four distinct patterns. The problem statement almost always tells you which one applies.
| Problem asks for... | Shape | Returns |
|---|---|---|
| "max/min/sum of tree" | A. Return value | a number |
| "does X exist?" | B. Return bool | True or False (stop early if found) |
| "find <strong>all</strong> paths/solutions" | C. Mutate external | nothing, just adds to result list |
| "max path" + needs subtree info | D. Hybrid | a value, and also updates a global |
Why best = [float('-inf')] and not best = float('-inf')? Python closures can read outer variables but cannot rebind them (without nonlocal). Wrapping in a list lets you mutate best[0] from inside the nested function.
Why max(dfs(node.left), 0)? Clamps negative subtrees to zero. If a subtree's best path is negative, drop it entirely rather than letting it drag down the sum.
Why return max(l, r) + node.val but update with l + r + node.val? The parent can only extend one branch, so we return the best single-branch path. But the global max might use both branches through this node, so we check that separately.
The Three Traversal Orders
Traversal order determines when the current node does its work relative to its children. The choice depends on the problem shape: whether the node needs information before going deeper, needs to process children in sorted order, or needs child results before it can compute its own answer.
Tree Traversal Orders
Step 1 of 14 · Process root first, then recurse. Used for tree serialization.
Pre-order: Process node, then children
Use pre-order when the node's work must happen before its children exist or are processed. Cloning a tree requires creating the parent node before attaching its children. Serializing a tree records the root first so the deserializer can reconstruct the tree top-down.
In-order: Left child, then node, then right
Use in-order when the problem depends on sorted order within a BST. In-order traversal visits BST nodes from smallest to largest. BST validation checks that each visited value exceeds the previous one. Kth-smallest extraction stops after visiting exactly k nodes.
Post-order: Children first, then node
Use post-order when the parent's value depends on results from both children. Computing tree height requires knowing both subtree heights before taking the max. Computing diameter requires both subtree depths before summing them. This is the most common order in DFS problems.
| Order | When to use | Example problems |
|---|---|---|
| Pre-order | Node must be created or recorded before children are processed | Clone tree, serialize tree |
| In-order | Problem requires sorted-order access in a BST | BST validation, kth smallest in BST |
| Post-order | Parent answer depends on child results | Max depth, tree diameter, delete tree |
Code Templates
The only difference between these three is where you place the "process node" line:
The concatenation version ([node.val] + left + right) is easier to read but creates new lists at every call, making it O(n²). The accumulator version appends in-place for O(n).
• Before going deeper? Pre-order (cloning, serialization)
• In sorted order for BST? In-order
• After I know child results? Post-order (height, diameter, most problems)
Family 1: Tree Recursion
Tree recursion is the most common DFS family. Each call owns exactly one subtree. There are no cycles, so no visited set is needed. The parent calls left and right children, waits for both results, then combines them.
Almost every tree DFS follows this structure. The only things that change are the base case return value, the recursive calls, and the combine step.
Three decisions completely determine your solution: the base case return value (0, True, -inf), what you do with the left and right results, and how you combine them with the current node.
Concrete Example: Max Depth
The base case returns 0 because an empty subtree contributes no depth. Each node returns the larger child depth plus one. The root's return value is the tree's maximum depth.
Worked Example: Path Sum II
Problem: find all root-to-leaf paths where the sum equals target. This combines downward parameters (remaining sum, current path) with mutation (appending to a result list). No value flows back up.
remaining - node.val: Immutable integer, so each branch automatically gets its own copy. No cleanup needed.
path.append / path.pop(): The path list is shared mutable state. After exploring the branch that includes the current node, pop() restores the path so the next sibling sees the correct state.
path.copy(): Without this, every saved path points to the same list object, which keeps changing as traversal continues.
remaining == node.val: We subtract before recursing into children, so at the leaf we compare the remaining amount to the leaf's own value.
max(child, 0) so you can drop an entire subtree instead of being forced to include it. Without this, a subtree with sum -5 drags down every path that passes through it.Family 2: Graph Components
Unlike trees, graphs can have cycles and multiple paths to the same node. The visited set prevents infinite loops by ensuring each node is processed exactly once. Once a node enters the visited set, it is finalized and no other DFS call will process it again.
Graph DFS · Visited Set
ENTER A
Pick any unvisited node. Order does not affect correctness.
Step 1 of 26
The key difference from tree DFS is the visited set. Check before processing, add immediately before exploring neighbors.
if node in visited: return: Prevents infinite loops on cyclic graphs. Without this guard, DFS revisits the same node endlessly through back edges.
visited.add(node) before the loop: Must happen before exploring neighbors. If you mark after, another path can reach this node before it is marked, causing duplicate processing.
for neighbor in graph[node]: Iterates over the adjacency list. In trees you access .left/.right directly. In graphs you iterate over all neighbors.
Connected Components
To count connected components, iterate over all nodes and start DFS from each unvisited one. Each DFS call marks an entire component as visited. The number of DFS initiations equals the number of components.
Family 3: Grid Flood Fill
Grids are implicit graphs where each cell connects to its 4 (or 8) adjacent cells. There is no explicit adjacency list. Bounds checking replaces it. Cells are often marked visited in-place by changing their value, which eliminates the need for a separate visited set.
Grid DFS · Number of Islands
Scan grid row-by-row for unvisited land
Two layers: outer scan finds islands, inner DFS explores each one.
Step 1 of 18
Each DFS call checks bounds and cell value before proceeding. If the cell is out of bounds, already visited, or not the target value, the call returns immediately. Otherwise it marks the cell and recurses in four directions.
Counting Islands
Scan every cell. When you find unvisited land, start a DFS to mark the entire connected island. The number of DFS initiations equals the number of islands.
visited = set() and visited.add((r, c)).Family 4: Cycle Detection
Detecting cycles in a directed graph requires 3 states, not 2. A standard visited set cannot distinguish between a node on the current DFS path (cycle if revisited) and a node fully explored in an earlier call (safe to reach again).
Cycle Detection · 3-State Coloring
ENTER node 3
Process this leaf first to demonstrate the DONE state.
Step 1 of 17
state[node] == 1: This node is on the current DFS path. Reaching it again means we followed a cycle back to an ancestor still being explored.
state[node] == 2: This node was fully explored in an earlier DFS call. Reaching it is safe. Another path leads here, but no cycle.
state[node] = 2 after the loop: All descendants explored with no cycle found. Marking as done prevents re-exploring this subgraph from other entry points.
for node in range(n) at the bottom: The graph may be disconnected. Starting DFS only from node 0 would miss cycles in unreachable components.
Family 5: Post-Order Aggregation
Some problems require each node to compute a value that depends on both children's results, and also to update a separate global answer. The return value flows up to the parent. The global update captures the best answer seen across the entire tree.
The classic example is Binary Tree Maximum Path Sum. A path can bend through a node, using both left and right branches. But the value returned to the parent can only extend through one branch, because a path cannot split.
max(dfs(node.left), 0): Clamps negative subtrees to zero. If a subtree's best path is negative, drop it entirely rather than letting it drag down the sum.
best[0] = max(best[0], l + r + node.val): The global answer can use both branches through this node, because the path bends here. This is checked at every node.
return max(l, r) + node.val: The parent can only extend one branch. A path cannot split at two different nodes. So the return value picks the better side.
The same hybrid pattern applies to tree diameter (return depth to parent, update global with left + right) and similar problems where the best answer passes through some node using both subtrees.
DFS vs BFS
The most common mistake is using DFS for shortest-path problems. BFS processes all nodes at distance d before any node at distance d + 1, so the first time it reaches a target is the shortest path. DFS has no such guarantee. It can reach a node via a long detour first.
DFS vs BFS · Finding Path from S to G
dfs(S)at Squeue.append(S)at SStep 1 of 6
| Problem shape | Use | Why |
|---|---|---|
| "shortest path" / "minimum steps" | BFS | BFS expands in distance order. Every node at distance d is processed before distance d + 1, so the first arrival is the shortest. |
| "nearest X" / "closest to" | BFS | BFS finds nodes in order of increasing distance. The first match is the closest by definition. |
| "level by level" / "each depth" | BFS | Each iteration of the BFS loop processes exactly one level, making level-order traversal natural. |
| "all paths" / "every solution" | DFS | DFS explores one complete branch before trying the next, which naturally enumerates all possibilities. |
| "does path exist" (any path) | DFS | DFS finds any valid path by following one branch to completion. No distance guarantee needed. |
| "compute from subtrees" | DFS | Post-order DFS computes child results before the parent, which is required when the parent depends on subtree values. |
| "cycle detection" | DFS | Three-state tracking (unvisited, visiting, done) maps directly to DFS recursion entry and exit. |
| "connected components" | Either | Both traverse all reachable nodes from a starting point. DFS is typically shorter to write. |
Complexity Analysis
Time and space complexity differ by structure type.
Tree DFS
- Time: O(n) because we touch each node exactly once and do constant work at each one.
- Space: O(h) where h is the tree height. The call stack grows as deep as the tree. For a balanced tree that's O(log n), but a skewed tree (every node has only one child) is O(n).
Graph DFS
- Time: O(V + E) because we visit each vertex once and look at each edge once when checking neighbors.
- Space: O(V) for the visited set, plus O(V) for the recursion stack in the worst case (a long chain of nodes).
Grid DFS
- Time: O(m x n) because we visit each cell at most once.
- Space: O(m x n) in the worst case. Imagine a snake-like path that visits every cell before backtracking.
| Problem type | Time | Space |
|---|---|---|
| Tree traversal | O(n) | O(h) |
| Graph traversal | O(V+E) | O(V) |
| Grid (m x n) | O(m x n) | O(m x n) |
| Cycle detection | O(V+E) | O(V) |
Common Pitfalls
Six common DFS bugs. Each passes simple test cases but fails on edge inputs.
Missing Base Case
The trap: When node is None, node.left throws an error. Even if it didn't, recursion would never terminate.
Fix: Always add if node is None: return base_value first.
Late Visited Marking
The trap: You can revisit the same node through different paths before it's marked visited. This causes infinite loops in graphs with cycles.
Fix: Add to visited before processing neighbors.
Forcing Negative Branches Into the Path
The problem: This always adds the best child path to the current node, even when that child path is negative. A subtree with sum -5 drags down every path that passes through it, but the code has no way to drop it.
Fix: Clamp child contributions with max(left, 0). This lets the node ignore a negative subtree entirely instead of being forced to include it.
Two-State Directed Cycle Detection
The trap: You can't distinguish between a node in the current path (cycle) and a node finished earlier (safe).
Fix: Use 3 states: 0=unvisited, 1=visiting, 2=done. Only state 1 indicates a cycle.
Overcomplicated Parameter Type
The trap: Using a mutable list when an immutable int works fine adds complexity. Now you need cleanup, copies, and there's more room for bugs.
Rule: Use immutable (int, tuple) when you only need an aggregate. Use mutable (list) only when you need the actual sequence.
Inconsistent Return and Mutate
The trap: This code tries to do both patterns at once but does neither correctly. It's unclear what the function is supposed to do.
Fix: Pick one pattern and be deliberate. If you need hybrid (like Max Path Sum), clearly separate what you return vs what you update globally.
When DFS Breaks
DFS is not the right tool for every traversal problem. Recognizing when it fails is as important as knowing how to use it.
Shortest Path in Unweighted Graphs
DFS can find a path, but it has no guarantee that the path is the shortest. DFS follows one branch to completion before trying others, so it can reach a node via a long detour before discovering the short route. BFS processes all nodes at distance d before distance d + 1, so the first arrival is always the shortest path.
Stack Overflow on Deep Inputs
Python's default recursion limit is about 1000 frames. A linked-list-shaped tree with 10,000 nodes will crash recursive DFS. For inputs that can be arbitrarily deep, convert to iterative DFS using an explicit stack, or increase the recursion limit (which risks real stack overflow at the OS level).
Missing Visited Set on Graphs
Treating a graph as a tree (no visited set) causes infinite recursion on any cycle. This is especially common with grid problems where students forget to mark cells, and with undirected graphs where the edge back to the parent creates an immediate cycle if not handled.
Level-Order Requirements
Problems that need to process nodes level by level, such as finding the rightmost node at each depth or computing level averages, are naturally solved with BFS. DFS can be adapted (by passing a depth parameter and grouping by depth), but BFS handles this without extra bookkeeping because it processes one complete level per iteration.
Iterative DFS
Two scenarios require iterative DFS: inputs deeper than the call stack limit (~1000 in Python), and problems that need pause/resume (BST iterator). Convert using an explicit stack.
Pre-order (Simple)
Why push right before left? The stack is LIFO (last in, first out). If we push right first, then left, we pop left first. This matches recursive left-to-right order.
Post-order (Tricky)
Post-order is harder iteratively because you need to process a node after both children. The key technique: track whether a node's children have already been processed.
In-order (BST Iterator Pattern)
In-order iterative is essential for BST problems that need pause/resume, like the BST iterator.
- Deep trees (avoid stack overflow)
- Need fine-grained control over traversal
- Languages with small call stacks
In interviews, recursive is usually preferred for clarity. Mention iterative as an optimization if asked about stack overflow.
Practice Problems
DFS problems cluster into tree traversals and graph explorations.
Tree DFS
| Problem | Difficulty | Approach |
|---|---|---|
| Maximum Depth of Binary Tree | Easy | Return 1 + max(left, right). Base case: null returns 0. The classic "return value up" pattern. |
| Path Sum | Easy | Pass remaining sum down. At leaf, check if remaining equals node value. No need to track the path itself. |
| Same Tree | Easy | Compare nodes at each position. Both null = same. One null = different. Both exist = compare values and recurse. |
| Validate Binary Search Tree | Medium | Pass valid range (min, max) down. Each node must be within range. Update range when going left (max=node) or right (min=node). |
| Lowest Common Ancestor | Medium | If current node is p or q, return it. If left and right both return non-null, current is the LCA. Otherwise propagate the non-null result. |
| Diameter of Binary Tree | Medium | Diameter passes through some node. At each node, calculate left_depth + right_depth. Return single-side max to parent, track global max separately. |
| Binary Tree Maximum Path Sum | Hard | A path can start and end anywhere. At each node, compute "through this node" (left + node + right) for global max, but return "extendable path" (node + max(left, right)) to parent. |
Graph DFS
| Problem | Difficulty | Approach |
|---|---|---|
| Clone Graph | Medium | Use hash map: original node → cloned node. Before recursing, check if already cloned. This handles cycles and prevents infinite recursion. |
| Course Schedule | Medium | Cycle detection in directed graph. Use three states: unvisited, in-progress, completed. Back edge (hitting in-progress) means cycle exists. |
| Course Schedule II | Medium | Topological sort via DFS. Add node to result after all descendants are processed (post-order). Reverse at the end. Detect cycles same as Course Schedule. |
| Pacific Atlantic Water Flow | Medium | Reverse the problem: DFS from ocean edges inward, marking cells that can reach each ocean. Answer is intersection of both sets. |
| Number of Connected Components | Medium | Standard connected components. Loop through all nodes; if unvisited, DFS to mark component. Count DFS initiations. |
Grid DFS
| Problem | Difficulty | Approach |
|---|---|---|
| Number of Islands | Medium | Mark connected land cells as visited using DFS from each unvisited land cell |
| Max Area of Island | Medium | Track island size by counting cells during DFS traversal |
| Surrounded Regions | Medium | DFS from border O cells to mark safe ones, then flip remaining O to X |
| Word Search | Medium | Backtracking DFS trying each direction, mark visited to avoid reuse |
Reference Templates
Compact code shapes for quick recovery. Each template shows the minimal structure for its family.
Base Case Reference
| Combine operation | Base case | Why |
|---|---|---|
| max(l, r) + 1 | 0 | Empty contributes 0 depth, leaf becomes max(0,0)+1 = 1 |
| l + r + 1 | 0 | Empty contributes 0 nodes, leaf becomes 0+0+1 = 1 |
| l and r | True | Empty is vacuously valid, only fails when a node violates |
| l or r | False | Empty has no valid path, only succeeds when a path is found |
Pattern Recap
Tree Recursion. Each call owns one subtree. No visited set needed. The parent waits for both children, then combines their results.
Graph Components. Visited nodes are finalized. Mark before exploring neighbors. Count components by counting DFS initiations from unvisited nodes.
Grid Flood Fill. Marked cells belong to a component. Bounds checking replaces the adjacency list. In-place marking eliminates the need for a separate visited set.
Cycle Detection. Three states distinguish nodes on the current path (visiting) from nodes fully explored in earlier calls (done). Only reaching a visiting node indicates a cycle.
Post-Order Aggregation. Child results must be known before the parent computes. The return value flows to the parent. A separate global variable captures the best answer across the whole tree.
Rebuilding the Pattern
When DFS feels unclear on a new problem, start with five questions.
First, identify the structure. Trees have no cycles. Graphs may have cycles and need a visited set. Grids are implicit graphs with bounds checking instead of an adjacency list.
Second, determine what state flows down from parent to child. Running totals, paths, bounds, depth, and parent references are the common parameter patterns. Immutable values (integers, tuples) need no cleanup. Mutable values (lists) require backtracking after each branch.
Third, determine what flows back up. Return a scalar when the parent needs a single aggregate. Return a boolean when the parent needs to short-circuit. Mutate an external list when collecting multiple answers. Use hybrid (return plus global update) when the best answer passes through a node using both subtrees.
Fourth, choose the traversal order. Pre-order if the node must be processed before its children. In-order if the problem needs sorted BST access. Post-order if the parent depends on child results. Most DFS problems are post-order.
Fifth, determine what prevents revisiting or infinite recursion. Trees need no protection. Graphs use a visited set marked before exploring neighbors. Directed graphs with cycle detection use three states. Grids mark cells in-place.
The pattern is recoverable from these five decisions: what structure you are exploring, what context each node needs from its parent, what each call returns, when the node does its work, and how revisiting is prevented.
Check Your Understanding
Use these questions to check whether you can reason through the pattern without looking at the template.
Ready to test your understanding?
13 questions covering DFS families, parameters, and traversal patterns.
Practice this pattern
Apply the guide to complete interview problems with explanations and code.
Learn Depth-First Search in a guided sequence
The Interview Course connects this pattern to its prerequisites, worked lessons, and progressively harder problems.