Coding interview pattern
Go as deep as possible before backtracking; the backbone of tree and graph exploration.
The idea
Depth-first search dives down one path until it can go no further, then backtracks and tries the next branch. It is naturally recursive (the call stack is the traversal stack) but can be written iteratively with an explicit stack. On trees it gives the preorder, inorder, and postorder traversals; on graphs it discovers connected components, detects cycles, and produces topological orders.
DFS shines when you need to explore all paths, reason about subtrees, or carry state down a branch and combine results coming back up. Postorder DFS in particular (process children before the parent) is the engine behind a huge class of tree problems: computing height, diameter, the lowest common ancestor, and any answer that depends on aggregating subtree results. The pattern of return a value from each child and combine them at the parent is worth internalising.
On grids and implicit graphs DFS does flood fill: from a starting cell, recurse into every connected matching neighbour, marking visited as you go. The choice between DFS and BFS often comes down to the question: DFS for exhaustive exploration, path enumeration, and subtree aggregation; BFS when the shortest path or the level matters.
Recognition
Cost
| Operation | Time | Space |
|---|---|---|
| Graph DFS | O(V + E) | O(V) stack |
| Tree DFS | O(n) | O(h) for height h |
| Grid flood fill | O(r*c) | O(r*c) worst case |
Worked example
Translatable skeleton
Language-agnostic on purpose. Translate it to your language of choice.
def dfs(node): if not node: return base; left = dfs(node.left); right = dfs(node.right); return combine(node, left, right)Practice
Work these in order, easy to hard. Each is chosen to drill a different facet of the pattern.
| Problem | Level | Why it fits |
|---|---|---|
| Maximum Depth of Binary Tree | Easy | Postorder height computation. |
| Number of Islands | Medium | DFS flood fill of connected land. |
| Clone Graph | Medium | DFS with a node-to-clone map. |
| Course Schedule | Medium | Cycle detection via DFS colouring. |
| Diameter of Binary Tree | Easy | Postorder, track the best through-node path. |
| Pacific Atlantic Water Flow | Medium | DFS from the borders inward. |
Avoid these
In the interview
Recognising the pattern is half the score; saying the right things out loud is the other half. These are the sentences that earn the signal.
State whether you need preorder, inorder, or postorder before you recurse, because the order is the whole answer for many tree problems and naming it shows you understand why.
For postorder subtree-aggregation problems, describe the contract of the recursive call, what each child returns and how the parent combines them, before writing the body; that contract is the design.
If the input could be deeply skewed, mention the recursion-depth risk and that you could switch to an explicit stack; interviewers like seeing you anticipate stack overflow.
dfs traversal - recursive tree traversal - connected components dfs
An external resource we recommend. AlgoExpert is not affiliated with us and we earn nothing from this link.
Keep going
Track a contiguous subarray or substring without re-scanning it from scratch.
Walk two indices toward or alongside each other to avoid a nested loop.
Halve the search space each step over any monotonic condition, not just sorted arrays.
Solve overlapping subproblems once, store the results, and build the answer up.
See all coding patterns, the coding questions for your role, and the behavioral round.