Pattern 8: DFS (Depth-First Search)

Deep Dive: DFS as Deep Exploration

All Paths from Source to Target (DAG)

Graph: 0 -> 1 -> 3
       0 -> 2 -> 3

DFS from 0:
  Path: [0]
    -> explore 1: path [0,1]
      -> explore 3: path [0,1,3] GOAL! Record it.
      -> backtrack to [0,1], backtrack to [0]
    -> explore 2: path [0,2]
      -> explore 3: path [0,2,3] GOAL! Record it.

All paths: [[0,1,3], [0,2,3]]

Cycle Detection with 3 Colors

WHITE (0) = unvisited
GRAY  (1) = in current DFS path (on the recursion stack)
BLACK (2) = fully processed

Visit node -> color GRAY
  If neighbor is GRAY -> CYCLE (we looped back!)
  If neighbor is BLACK -> safe (already done)
  If neighbor is WHITE -> recurse
Finish node -> color BLACK

---

Signal: Explore all paths, tree/graph traversal, connected components, cycle detection Template: dfs() / dfs_grid() in templates.py

When to Use

• "All paths from source to target"
• "Number of islands / connected components"
• Tree traversals (inorder, preorder, postorder)
• Cycle detection in directed graphs (white/gray/black coloring)

Re-solve from Phase 1-2 (TIMED)

Problem	Source	Target Time	Done?
Number of Islands	Phase 2.4	15 min	[ ]
Maximum Depth of Binary Tree	Phase 1.7	8 min	[ ]
All Paths from Source to Target	Phase 2.4	20 min	[ ]

New Practice Problems

Add problems to solutions/ and enrich as needed.

---

First-time Recognition Signals

When you read a brand-new problem statement, this pattern is the right tool if you see:

• "Find / count / enumerate all paths or all configurations" in a tree or graph — DFS naturally explores down a branch then backtracks.
• "Number of connected components / number of islands" in a grid or graph — flood-fill with DFS from each unvisited cell.
• "Tree problem requiring information aggregated from subtrees" (height, diameter, balanced check, sum, LCA) — post-order DFS so children return values to parents.
• "Detect a cycle in a directed graph" — DFS with white/gray/black coloring is the standard recipe.
• "Clone graph / serialize tree / mirror tree" — recursive DFS mirrors the recursive structure of the data.

Anti-signals (looks like this pattern, isn't)

• "Shortest path / minimum steps" in an unweighted graph — BFS, not DFS. DFS will find a path but not necessarily the shortest.
• "Process the graph level by level" — BFS is the natural fit; DFS would require carrying depth and grouping after the fact.
• "Topological order of a DAG" — Kahn's BFS is usually clearer than DFS post-order, though DFS post-order also works.