Pattern 09: DFS (Depth-First Search)

0. The Template (Copy-Paste Skeleton)

DFS is one recursive shape reused four ways. Pick your traversal order (when you touch the node) and whether you return a value up or carry state down.

// TEMPLATE A — TREE DFS, returning a value UP the call stack (post-order)
int dfs(TreeNode node) {
    if (node == null) return 0;                  // 1. BASE CASE — always first

    int left  = dfs(node.left);                  // 2. RECURSE on children
    int right = dfs(node.right);

    return combine(node.val, left, right);       // 3. COMBINE and return upward
}

// TEMPLATE B — TREE DFS, carrying state DOWN (path sum, depth, running prefix)
void dfs(TreeNode node, int running, List<Integer> path, List<List<Integer>> out) {
    if (node == null) return;

    running += node.val;
    path.add(node.val);                          // CHOOSE

    if (node.left == null && node.right == null && running == target) {
        out.add(new ArrayList<>(path));          // COPY — path is mutated after this
    }
    dfs(node.left,  running, path, out);         // EXPLORE
    dfs(node.right, running, path, out);

    path.remove(path.size() - 1);                // UN-CHOOSE (backtrack)
}

// TEMPLATE C — GRAPH / GRID DFS with a visited set
void dfs(int r, int c, char[][] grid, boolean[][] seen) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return;  // bounds
    if (seen[r][c] || grid[r][c] == '0') return;                            // visited/blocked

    seen[r][c] = true;
    for (int[] d : DIRS) dfs(r + d[0], c + d[1], grid, seen);
}

// TEMPLATE D — ITERATIVE DFS (when recursion depth is a risk: n up to 10^5)
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
    TreeNode node = stack.pop();
    visit(node);
    if (node.right != null) stack.push(node.right);   // push RIGHT first
    if (node.left  != null) stack.push(node.left);    // so LEFT pops first (pre-order)
}

The three traversal orders — the only thing that changes is where you visit()

    PRE-ORDER   visit(node); dfs(left); dfs(right);   → copy/serialize a tree, root-first
    IN-ORDER    dfs(left); visit(node); dfs(right);   → SORTED output on a BST
    POST-ORDER  dfs(left); dfs(right); visit(node);   → children before parent: heights,
                                                        deletion, bottom-up aggregation

Decision guide

Question	Shape
height / depth / diameter / “is balanced”	A — post-order, return up
root-to-leaf paths, path sum, all combinations	B — carry down + backtrack
number of islands, flood fill, connected components	C
validate a BST	in-order (must be strictly increasing), or carry (min, max) down
n ≈ 10^5 nodes / a degenerate linked-list-shaped tree	D — recursion would StackOverflow

The two classic bugs

1. out.add(path) instead of out.add(new ArrayList<>(path)). You stored a reference to a list you’re about to mutate — every result ends up identical (usually empty).
2. Forgetting to un-choose. Every path.add needs a matching path.remove on the way out, or state leaks into sibling branches.

---

1. Pattern Identification & Logic

How to Identify (Interview Triggers)

• “Find all paths” from root to leaf
• “Height / Depth / Diameter” of a tree
• “Check if a property holds for the entire tree” (balanced, symmetric)
• “Lowest Common Ancestor” or “split point” between two nodes
• Need to process children before parent (post-order)

The Algorithm (Pseudocode)

Pre-order (Root → Left → Right):

dfs(node):
    if node is null: return
    process(node)
    dfs(node.left)
    dfs(node.right)

Post-order (Left → Right → Root) - “Bottom-Up”:

dfs(node):
    if node is null: return base_value
    leftResult = dfs(node.left)
    rightResult = dfs(node.right)
    return combine(leftResult, rightResult, node)

The ‘Trick’ to Know

• Bottom-Up vs. Top-Down: If the answer at a node depends on its children’s answers, use post-order (bottom-up). If you’re passing constraints down, use pre-order (top-down).
• Global vs. Local state: For problems like “Maximum Path Sum”, the recursive function returns a “local” value (single path), but updates a “global” variable (best path through any node).

---

2. Java Implementation (Brute Force vs. Optimal)

Example Problem: Maximum Depth of Binary Tree - LC 104

Optimal: Bottom-Up DFS - O(n)

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);

        return 1 + Math.max(leftHeight, rightHeight);
    }
}

Example Problem: Lowest Common Ancestor - LC 236

Brute Force: Store Paths - O(n) time, O(n) space

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pathP = new ArrayList<>();
        List<TreeNode> pathQ = new ArrayList<>();

        findPath(root, p, pathP);
        findPath(root, q, pathQ);

        TreeNode lca = root;
        for (int i = 0; i < Math.min(pathP.size(), pathQ.size()); i++) {
            if (pathP.get(i) == pathQ.get(i)) {
                lca = pathP.get(i);
            } else {
                break;
            }
        }
        return lca;
    }

    private boolean findPath(TreeNode root, TreeNode target, List<TreeNode> path) {
        if (root == null) return false;
        path.add(root);
        if (root == target) return true;
        if (findPath(root.left, target, path) || findPath(root.right, target, path)) return true;
        path.remove(path.size() - 1);
        return false;
    }
}

Optimal: Post-Order Result Bubbling - O(n) time, O(h) space

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) return root;

        return (left != null) ? left : right;
    }
}

Java Architecture Insights

• Reference comparison (==) for TreeNode: We compare object identity, not values. root == p checks if it’s the exact same node in memory.
• Recursion depth limit: Default JVM stack is ~512KB. For a skewed tree with 10^5 nodes, this could overflow. Mention iterative alternatives in interviews for bonus points.
• 1 + Math.max(left, right) template: Reusable for height, diameter, balanced-tree checks. The “1+” represents the current node’s contribution.

---

3. Mental Model & Visualization

ASCII Diagram: Max Depth

      3
     / \
    9   20          maxDepth(3)
       /  \          ├── maxDepth(9) → 1
      15   7         └── maxDepth(20)
                          ├── maxDepth(15) → 1
                          └── maxDepth(7)  → 1
                         (20 returns 1+max(1,1) = 2)
                    (3 returns 1+max(1,2) = 3)

ASCII Diagram: LCA (p=5, q=1)

      3
     / \
    5   1
   / \ / \
  6  2 0  8

LCA(3):
 ├── LCA(5) → returns 5 (base case: root == p)
 └── LCA(1) → returns 1 (base case: root == q)
Both non-null → return 3 (the split point)

Senior Mental Trigger

“Need children’s answers before deciding at parent = post-order DFS (bottom-up bubble).”

---

4. Curated Problem Lists

Commonly Asked (Bread & Butter)

#	Problem	Difficulty
LC 104	Maximum Depth of Binary Tree	Easy
LC 226	Invert Binary Tree	Easy
LC 100	Same Tree	Easy
LC 112	Path Sum	Easy
LC 236	Lowest Common Ancestor	Medium

FAANG ‘Aha!’ Level (Hard/Unintuitive)

#	Problem	Difficulty
LC 124	Binary Tree Maximum Path Sum	Hard
LC 543	Diameter of Binary Tree	Easy
LC 105	Construct Tree from Preorder/Inorder	Medium
LC 297	Serialize and Deserialize Binary Tree	Hard
LC 979	Distribute Coins in Binary Tree	Medium
LC 968	Binary Tree Cameras	Hard

---

5. Time & Space Complexity Table

Approach	Time	Space	Notes
DFS Recursive	O(n)	O(h)	h = height, worst case O(n) skewed
DFS Iterative	O(n)	O(h)	Explicit stack, avoids stack overflow
BFS	O(n)	O(w)	w = max width, different traversal

---

5 Pattern Variations

Pattern Name	When to Use	Template
Bottom-Up (Post-order)	Height, diameter, LCA	1 + max(left, right)
Top-Down (Pre-order)	Validate BST, pass constraints down	dfs(node, min, max)
Path Tracking	Path Sum, all root-to-leaf paths	Add to path, recurse, backtrack
Global + Local	Max path sum, diameter	Return local, update global