Depth-First Search (DFS)

🧠 Mental Model

The recursion call stack is the traversal stack. That's why DFS is so short to write recursively — the language manages the stack for you. Two moments matter:

• Pre-order (on the way down, when you first enter a node) — good for "visit/mark."
• Post-order (on the way back up, after children are done) — the backbone of topological sort and Tarjan's (Weeks 3–4).

⚙️ Mechanics

1. Mark the current node visited.
2. For each unvisited neighbor, recurse into it.
3. (Optional post-order work here, after the loop.)

Recursive vs Iterative

Recursive is cleaner and preferred in interviews unless depth can exceed the stack limit (~10⁴–10⁵ frames in Java). For very deep graphs, convert to an explicit stack. Note: an iterative stack-based DFS visits nodes in a slightly different order than recursion, which is fine for reachability but matters if you rely on strict pre/post ordering.

Path tracking & backtracking

To enumerate all paths (not just reachability), add the node to a path list before recursing and remove it after — that "undo" is backtracking. Here visited marking is often not used (you may revisit a node on a different path).

📊 Complexity

💻 Reference Implementation (Java)

Recursive DFS (grid flood variant) plus the iterative form for reference.

import java.util.*;

/** Recursive DFS on a grid — counts cells in one region. */
public int dfs(int[][] grid, int r, int c, boolean[][] seen) {
    int rows = grid.length, cols = grid[0].length;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return 0; // bounds
    if (seen[r][c] || grid[r][c] == 0) return 0;      // visited or water

    seen[r][c] = true;                                    // pre-order: mark on entry
    int count = 1;
    count += dfs(grid, r+1, c, seen);
    count += dfs(grid, r-1, c, seen);
    count += dfs(grid, r, c+1, seen);
    count += dfs(grid, r, c-1, seen);
    return count;                                       // post-order: aggregate on the way up
}

/** Iterative DFS on an adjacency list — when recursion depth is a risk. */
public void dfsIterative(List<Integer>[] adj, int start) {
    boolean[] seen = new boolean[adj.length];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        int u = stack.pop();
        if (seen[u]) continue;     // mark on POP here (may be pushed twice)
        seen[u] = true;
        for (int v : adj[u]) if (!seen[v]) stack.push(v);
    }
}

⚠️ Common Pitfalls

🎯 Problems