What it is
Depth-first search walks a tree, graph, or grid by committing to one neighbor (or child) and going all the way down before trying the next one, either with explicit recursion or a manual stack. On a tree that recursion is the traversal itself; on a graph or grid you additionally track which nodes or cells you have already visited so you don't loop forever on a cycle. Most of the value is in what you compute on the way down (top-down: pass state to children) or on the way back up (bottom-up: return a value each call reports to its parent), not in the traversal order alone.
When it applies
- You need a property of a tree that depends on both subtrees at once: a height, a diameter, a "best path through this node," a balance check.
- You need to explore every reachable node or cell from a start point — connected components, flood fill, cycle detection, deep-copying a graph.
- The state naturally nests: a recursive call's answer is built from its children's answers, or you're trying every branch of a search space (word paths on a grid, pattern matching over a trie).
- Finding the shortest path or the fewest steps in an unweighted graph calls for BFS, not this — since DFS finds a path, not the shortest one. Counting nodes level by level also belongs to BFS.
Tells in the problem
- "Given the root of a binary tree, return..." where the answer needs information from both children before it can be computed at the parent.
- "Connected," "reachable," "same island/group," or "deep copy" over a graph or grid.
- A path or subtree condition that depends on everything below a node, not just its immediate children.
- Grid problems where you flood-fill from a cell and mark visited cells so you don't recount or reprocess them.
- A search space where you try one choice, recurse, and undo the choice if it doesn't pan out.
The classic mistake
The most common failure is doing real work more than once because a value that should be computed bottom-up (post-order) gets recomputed at every level instead, turning an O(n) walk into O(n²) — checking a subtree's height from scratch at every node instead of returning it while you're already there. The fix is to have the recursive call return the value the parent needs (a height, an "is this side balanced," a "best downward path here"), so each subtree is visited once, and the parent only combines results. Notice this in yourself when you find you're calling a helper function inside another traversal function that walks the same nodes again.
Questions to start with
- Maximum Depth of Binary Tree — the plainest post-order DFS: each call returns one number to its parent.
- Invert Binary Tree — same shape, but you mutate the tree on the way through instead of just reading it.
- Balanced Binary Tree — introduces the trap of recomputing a subtree property at every level, and the sentinel-value fix.
- Number of Islands — moves DFS from trees to a grid: flood fill and marking visited cells.
- Clone Graph — DFS over a graph with cycles, where you must register a node before recursing into its neighbors to avoid infinite recursion.
- Binary Tree Maximum Path Sum — the hardest step up: separate the value a call returns upward from the value it records as a candidate answer.