Interview Cake Depth-first search (DFS) is an algorithm for exploring a tree or graph. It goes as deep as possible down one path before backing up and trying a different one, using a stack (often just the call stack, via recursion) to remember where to back up to. Since it visits every node and edge once, it takes O(V + E) time.
| On a graph | On a tree | |
|---|---|---|
| time | O(V + E) | O(n) |
| space | O(V) | O(h) |
V is the number of nodes (vertices) and E is the number of edges in the graph. n is the number of nodes in the tree, and h is its height.
Depth-first search is like walking through a corn maze. You explore one path, hit a dead end, and go back and try a different one.
Here's how a DFS would traverse this tree, starting with the root:
We'd go down the first path we find until we hit a dead end:
Then we'd do the same thing again—go down a path until we hit a dead end:
And again:
And again:
Until we reach the end.
How DFS Works
- Start at a node and mark it as visited.
- Pick a neighbor you haven't visited yet, and run a DFS from there.
- When a node has no unvisited neighbors left, back up to the node you came from and keep going.
Here's a recursive implementation that returns the nodes in the order the search visits them:
The visited hash set is what keeps a DFS from going around in circles forever when a graph has a cycle. (In a tree, there's only one path to each node, so you can skip it.) You can also write a DFS without recursion, by pushing nodes onto your own stack. That's handy when the graph is so deep that recursion would overflow the call stack.
DFS vs. BFS
Depth-first search is often compared with breadth-first search (BFS), which explores the graph level by level instead:
| DFS | BFS | |
|---|---|---|
| Explores | As deep as possible down one path, then backs up | All nodes one step away, then two steps away, and so on |
| Uses a | Stack (or recursion) | Queue |
| Time | O(V + E) | O(V + E) |
| Extra space on a tree | O(h), for the height of the tree | O(w), for the width of the widest level |
| Finds shortest paths? | No | Yes, in unweighted graphs |
| Great for | Detecting cycles, topological sorting, exploring every path (backtracking), and solving mazes | Shortest paths, finding the closest matches first, and level-by-level tree traversal |
A DFS on a binary tree generally uses less memory than a BFS, since a balanced tree's height is a lot smaller than the width of its bottom level. And DFS is easy to write with recursion. But if you need the shortest path to a node, use BFS.
What DFS Is Used For
- Detecting cycles in a graph.
- Topological sort, which orders tasks so each one comes after everything it depends on.
- Finding connected components, like counting the islands in a grid.
- Backtracking problems, like generating every permutation of a string or solving a maze.
- Tree traversals. Pre-order, in-order, and post-order traversals are all depth-first.
See also:
Interview coming up?
Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.
No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.
No spam. One-click unsubscribe whenever.
You're in! Head over to your email inbox right now to read day one!
