Depth-First Search
The Depth-First Search Pattern
Follow one path as far as it goes, then back up and try the next. On trees this gives the preorder, inorder and postorder traversals; on graphs it needs a visited set to avoid revisiting nodes.
Interactive problems
Free to open
How do you recognise a depth-first search problem?
You need to explore every node, test whether a path exists, work with tree structure, or compute something that depends on a node’s children before the node itself — the postorder shape behind most tree DP.
What is the time complexity of the depth-first search pattern?
O(V + E) time. Space is O(h) for the recursion stack, where h is depth — which is O(n) in the worst case for a skewed tree.
Depth-First Search practice problems
Each problem pairs a worked explanation with an interactive visualizer you step through yourself, plus the implementation in JavaScript, Python, Java and C++.
- Introduction to DFSFree
- DFS FundamentalsFree
- Return Values in DFSPro
- Invert Binary TreePro
- Maximum Depth of Binary TreePro
- Path SumPro
- Passing Values Down (State)Pro
- Validate Binary Search TreePro
- Kth Smallest Element in a BSTPro
- Construct Binary Tree from Preorder and Inorder TraversalPro
- Binary Tree TiltPro
- Diameter of Binary TreePro
- Lowest Common Ancestor of a Binary TreePro
- Path Sum IIPro
- Longest Univalue PathPro
- Graphs OverviewPro
- Graph Representation: Adjacency ListPro
- Clone GraphPro
- Graph Valid TreePro
- Matrices as GraphsPro
- Flood FillPro
- Types of DFS (Tree Traversals)Pro
- Number of IslandsPro
- Surrounded RegionsPro
- Pacific Atlantic Water FlowFree
Depth-First Search problems by difficulty and complexity
The difficulty, running time and extra space of every depth-first search solution on this page, as each lesson derives them.
| Lesson | Difficulty | Best | Average | Worst | Space |
|---|---|---|---|---|---|
| Introduction to DFS | Easy | Ω(n) | Θ(n) | O(n) | O(h) |
| DFS Fundamentals | Easy | Ω(n) | Θ(n) | O(n) | O(h) |
| Return Values in DFS | Easy | Ω(n) | Θ(n) | O(n) | O(h) |
| Invert Binary Tree | Easy | Ω(n) | Θ(n) | O(n) | O(h) |
| Maximum Depth of Binary Tree | Easy | Ω(n) | Θ(n) | O(n) | O(h) |
| Path Sum | Easy | Ω(h) | Θ(n) | O(n) | O(h) |
| Passing Values Down (State) | Medium | Ω(n) | Θ(n) | O(n) | O(h) |
| Validate Binary Search Tree | Medium | Ω(1) | Θ(n) | O(n) | O(h) |
| Kth Smallest Element in a BST | Medium | Ω(h + k) | Θ(h + k) | O(n) | O(h) |
| Construct Binary Tree from Preorder and Inorder Traversal | Medium | Ω(n) | Θ(n) | O(n) | O(n) |
| Binary Tree Tilt | Easy | Ω(n) | Θ(n) | O(n) | O(h) |
| Diameter of Binary Tree | Easy | Ω(n) | Θ(n) | O(n) | O(h) |
| Lowest Common Ancestor of a Binary Tree | Medium | Ω(1) | Θ(n) | O(n) | O(h) |
| Path Sum II | Medium | Ω(n) | Θ(n log n) | O(n²) | O(n) |
| Longest Univalue Path | Medium | Ω(n) | Θ(n) | O(n) | O(h) |
| Graphs Overview | Medium | Ω(V + E) | Θ(V + E) | O(V + E) | O(V + E) |
| Graph Representation: Adjacency List | Medium | Ω(V + E) | Θ(V + E) | O(V + E) | O(V + E) |
| Clone Graph | Medium | Ω(V + E) | Θ(V + E) | O(V + E) | O(V) |
| Graph Valid Tree | Medium | Ω(V + E) | Θ(V + E) | O(V + E) | O(V + E) |
| Matrices as Graphs | Medium | Ω(1) | Θ(m·n) | O(m·n) | O(m·n) |
| Flood Fill | Easy | Ω(1) | Θ(m·n) | O(m·n) | O(m·n) |
| Types of DFS (Tree Traversals) | Medium | Ω(n) | Θ(n) | O(n) | O(h) |
| Number of Islands | Medium | Ω(m·n) | Θ(m·n) | O(m·n) | O(m·n) |
| Surrounded Regions | Medium | Ω(m·n) | Θ(m·n) | O(m·n) | O(m·n) |
| Pacific Atlantic Water Flow | Medium | Ω(m·n) | Θ(m·n) | O(m·n) | O(m·n) |
Related patterns and concepts
The underlying technique is covered from first principles in the depth-first search lesson in the DSA visualizer curriculum. Depth-First Search is one of the 17 coding interview patterns, and its problems also appear in the DSA 75 interview sprint.