Coding interview pattern
Depth-First Search (DFS)
Go as deep as possible before backtracking; the backbone of tree and graph exploration.
The idea
How the depth-first search (dfs) pattern works
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
When to reach for it
- You need to visit or enumerate all nodes, paths, or subtrees.
- The answer aggregates results from children up to the parent (postorder).
- You are detecting cycles or finding connected components.
- Memory for a wide BFS frontier would be larger than the recursion depth.
Cost
Time & space complexity
| 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
Walkthrough: Maximum depth of a binary tree
- 1Base case: an empty node contributes a depth of 0.
- 2Recurse into the left and right children to get their depths.
- 3Combine: this node's depth is one plus the larger of the two child depths.
- 4Return that value up to the caller; the root's return is the answer.
- 5This postorder shape (children first, then combine) generalises to height, diameter, and balance checks.
Translatable skeleton
The shape in pseudocode
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
Curated problem set
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
Common pitfalls
- Stack overflow on deep or skewed inputs (consider an iterative stack).
- Forgetting to mark visited, causing infinite loops on cyclic graphs.
- Confusing preorder and postorder when the combine step depends on it.
- Mutating shared state across branches without restoring it.
In the interview
How to communicate it live
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.
Also searched as
dfs traversal - recursive tree traversal - connected components dfs
Last reviewed by the site editor: June 2026
An external resource we recommend. AlgoExpert is not affiliated with us and we earn nothing from this link.
Sources
- Lecture 10: Depth-First Search MIT OpenCourseWare, 6.006 Introduction to Algorithms
- 4.2 Directed Graphs (topological sort, cycle detection) Sedgewick and Wayne, Princeton University
- Tree traversal (depth first) Wikipedia
Build the toolkit
More patterns worth learning
Recognition wins coding rounds. The more shapes you can name on sight, the faster a solution arrives.
- Sliding Window
Track a contiguous subarray or substring without re-scanning it from scratch.
- Two Pointers
Walk two indices toward or alongside each other to avoid a nested loop.
- Binary Search
Halve the search space each step over any monotonic condition, not just sorted arrays.
- Dynamic Programming
Solve overlapping subproblems once, store the results, and build the answer up.
Round out your prep
See all coding patterns, the coding questions for your role, and the behavioral round.