When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Components
- Path existence
- Subtree aggregation
When another approach fits better
- The shortest unweighted distance is required
- Unbounded depth makes recursion unsafe without an iterative form
How it works#
Restart a traversal for every query or enumerate walks without retaining visited state.
Define node state: unseen, active, or complete when cycle semantics require it.
Mark at entry before exploring neighbors.
State what the call returns or what mutation it completes.
InvariantEach active frame owns one node and the unfinished neighbors or child results needed before that frame can resolve.
Example and template#
Number of Islands
Treat a grid as an implicit graph and mark each cell once.
Open the full problem brief- Enter A
stack: AA becomes visited before any neighbor is explored.
- Explore B
stack: A → BA pauses while B owns its branch; B's result returns to A.
dfs(node):
mark node seen
aggregate = base(node)
for neighbor of node:
if unseen:
aggregate = combine(aggregate, dfs(neighbor))
return aggregate- Time
- O(V + E)
- Space
- O(V) worst case
- Assumptions
- Each node/edge is processed a bounded number of times; recursion depth may reach V.
Pitfalls#
Common wrong approaches
Cycles can re-enter an active node indefinitely.
It complicates repeated calls and can obscure the subtree contract.
Edge cases
- Disconnected graph
- Self-loop
- Deep chain
- Mutating an input grid versus a visited set
Interview narration
- “I only need to know whether this region is reachable, so branch order is irrelevant.”
- “This call returns the aggregate for exactly one subtree/component.”
- “I mark on entry to prevent an active cycle from re-entering.”
Practice#
Number of Islands
Treat a grid as an implicit graph and mark each cell once.
Practice this problemFor each tree node, return whether its entire subtree satisfies a bound inherited from ancestors.
Reveal the pattern decision
Use DFS because each recursive frame carries bounds downward and returns subtree validity upward.
Transfer problem
Clone a graph with cycles while preserving sharing.
Checkpoint: Create and memoize a clone before descending into neighbors.
Follow-up variations
- Convert recursion to an explicit stack
- Use three colors to detect a directed back edge
Error-log prompts
- When was visited set?
- What exactly did one call return?