Follow each branch to the end before backtracking - the backbone of tree traversal, connectivity, and exhaustive search.
What depth-first search is
DFS commits to one branch until it dead-ends, then backs up and tries the next - implemented most naturally as recursion, where the call stack is the search stack. It visits every node and edge of a component, which makes it the engine behind connectivity ('how many islands'), reachability ('is there a path'), tree computations ('height, diameter, path sums'), and full enumeration.
Where BFS asks 'what is closest', DFS asks 'what exists down here'. Most tree problems are DFS whether or not anyone says the word: any recursive function on a tree is a depth-first traversal with work attached.
How to recognize it
Signals: counting or measuring connected regions, validating structure (is this a valid BST), aggregating over all root-to-leaf paths, cloning or serializing a graph, or any tree question at all. If the answer requires seeing an entire component or an entire subtree before deciding, DFS fits.
The discipline that separates clean solutions from tangles: decide what each recursive call returns and what it receives, before writing it. 'Return the height of this subtree', 'return whether a path with this remaining sum exists below here'. Once the contract is stated, the code writes itself; without it, you get global variables and bugs.
The subtree-contract template
Tree DFS problems reduce to: base case for null, recurse on children, combine. The combine step is where the problem actually lives. When information must flow down (like remaining sum), pass it as a parameter; when it flows up (like height), return it; when the answer is neither purely up nor down (like diameter), return the up-value and update a shared best as a side effect.
pseudocode
# contract: returns height of subtree; updates best (diameter) as side effect
def dfs(node):
if node is null: return 0
left = dfs(node.left)
right = dfs(node.right)
best = max(best, left + right) # path through this node
return 1 + max(left, right) # height, per the contract
Grid DFS and flood fill
A grid is a graph where each cell has up to four neighbors. DFS from a cell visits its whole region - that is flood fill. Mark cells visited as you enter them (mutating the grid or via a visited set), recurse in four directions with bounds checks, and count or measure regions by launching DFS from every unvisited land cell. Recursion depth equals region size in the worst case; on very large grids, convert to an explicit stack to avoid stack overflow, and say so proactively.
Common pitfalls
No visited marking on graphs with cycles - infinite recursion. Trees are the only place you may skip it.
Marking visited after recursing instead of before - the same cell gets entered from two directions.
Muddled return contracts: a function that sometimes returns a height and sometimes a diameter. One function, one contract; extra answers travel via parameters or an outer variable.
Validating a BST by only comparing each node with its children - the classic wrong answer. Correctness needs range bounds passed down: every node in a left subtree is bounded above by every ancestor it turned left at.
Recursion depth: a path-shaped tree or snake-shaped island recurses O(n) deep. Know your language's stack limit and the iterative rewrite.
Worked examples
1. Number of islandsmedium
Given a grid of '1' (land) and '0' (water), count the islands - groups of land connected horizontally or vertically.
Each island is a connected component; counting components means: scan all cells, and every time you find unvisited land, that is one new island - flood it so it is never counted again.
The flood is DFS: mark the cell as water (or visited), recurse into the four neighbors that are in bounds and still land.
The outer double loop plus inner flood touches each cell a constant number of times: O(rows x cols) total, despite the nested appearance.
Mention the two variations interviewers pivot to: BFS flood (same complexity, no stack risk) and union-find (when the grid mutates over time).
pseudocode
count = 0
for r in rows, c in cols:
if grid[r][c] == LAND:
count += 1
flood(r, c) # DFS: mark land -> water, recurse 4 ways
return count
def flood(r, c):
if out of bounds or grid[r][c] != LAND: return
grid[r][c] = WATER
flood(r+1,c); flood(r-1,c); flood(r,c+1); flood(r,c-1)
Remember: Counting components = scan + flood: the DFS erases each island exactly once, so the counter increments once per island.
2. Validate binary search treemedium
Determine whether a binary tree satisfies the BST property: every node is greater than all nodes in its left subtree and smaller than all in its right subtree.
The trap: checking only node vs. its immediate children accepts trees where a grandchild violates a grandparent's bound. The property is about entire subtrees.
Carry the allowed open interval (low, high) down the tree: root gets (-inf, +inf); going left tightens high to the node's value; going right tightens low.
Each node checks low < value < high, then recurses with narrowed bounds. Information flows downward as parameters - the contract choice is the whole solution.
O(n) time, O(height) stack. Alternative framing worth naming: an in-order traversal of a valid BST is strictly increasing.
pseudocode
def valid(node, low, high):
if node is null: return true
if not (low < node.val < high): return false
return valid(node.left, low, node.val)
and valid(node.right, node.val, high)
valid(root, -infinity, +infinity)
Remember: BST validity is an ancestor constraint, not a parent-child one - so the bounds must travel down through the recursion.
3. Binary tree maximum path sumhard
Find the maximum sum over all paths in a binary tree, where a path is any sequence of connected nodes and need not pass through the root.
Two quantities live at each node and must not be conflated: the best path that passes through this node (may use both children), and the best downward 'arm' this node can offer its parent (at most one child).
Contract: dfs(node) returns the best arm - node.val plus the larger child arm, floored at 0 because a negative arm is better dropped.
Side effect: at each node, candidate answer = node.val + left arm + right arm; keep a running maximum across all nodes.
One O(n) pass. The 'return one thing, record another' shape recurs in diameter, longest univalue path, and house-robber-on-tree - learn it once, reuse it everywhere.
pseudocode
best = -infinity
def dfs(node):
if node is null: return 0
left = max(0, dfs(node.left)) # negative arms are dropped
right = max(0, dfs(node.right))
best = max(best, node.val + left + right) # path through node
return node.val + max(left, right) # arm for the parent
dfs(root); return best
Remember: When a path may bend, each node returns its best straight arm upward while recording the best bent path locally - two roles, cleanly separated.
Check yourself
Try to answer before revealing - retrieving from memory is what makes it stick.
1What is the single most important design decision in a tree DFS solution?
Whether to use recursion or an explicit stack
✓ Defining exactly what each recursive call receives and returns before coding
Choosing pre-order versus post-order names
Minimizing the number of helper functions
A stated contract ('returns subtree height', 'receives remaining sum') makes the combine step mechanical. Most tangled DFS code comes from a function trying to return two different things.
2Why does comparing each node only to its direct children fail to validate a BST?
It is too slow
✓ The BST property constrains entire subtrees against every ancestor, so a deep node can violate a bound set levels above
It fails only on unbalanced trees
Children may be null
A right grandchild of a left child must still be smaller than the grandparent. Only bounds passed down the recursion - or an in-order scan checked for strict increase - capture that.
3Why is counting islands O(rows x cols) even though DFS runs inside a double loop?
Because DFS is O(1) per call
✓ Because each cell is flooded (visited) at most once across all DFS calls, so the total work is bounded by the grid size
Because most cells are water
It isn't - the worst case is quadratic in cells
Flooding marks land as visited, so no cell is ever processed twice. The outer scan plus all floods together touch each cell a constant number of times - classic amortized accounting.
4In maximum path sum, why does the recursion return only the best single 'arm' rather than the best path?
To save memory
✓ Because a parent extending a path can use at most one child branch - a bent path cannot bend twice
Because arms are always positive
Because paths must pass through the root
A path through the parent goes down into at most one child. The bent option (both arms) is legal only as a complete path, so it is recorded in the running best rather than returned.
5When must DFS track visited nodes?
Always
✓ On any graph that may contain cycles or multiple paths to a node; trees are the exception
Only on directed graphs
Only when using recursion
Cycles cause infinite recursion and shared nodes cause double-counting. Trees have unique paths from the root, so no marking is needed there.
Frequently asked questions
Is recursion required for DFS?
No - an explicit stack gives the same traversal and avoids stack-overflow on deep structures (path-shaped trees, snake-like grid regions). Recursion is usually clearer; mention the iterative fallback when input depth could reach tens of thousands.
How do I choose between DFS and BFS on a grid?
For region questions (count, area, fill) they are interchangeable - pick DFS for brevity or BFS to avoid deep recursion. For distance questions (nearest, fewest steps) only BFS is correct.
What are pre-order, in-order, and post-order in this framing?
They are just where the node's own work sits relative to the child recursions: before (copying/serializing), between (sorted output from BSTs), or after (heights, sums - anything needing children's results first). Choose by data dependency, not by habit.