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.
21
Interactive problems3
Free to openHow to 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.
Time and space complexity
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 DFS
- Maximum Depth of Binary Tree
- Path Sum
- Passing Values Down (State)
- Validate Binary Search Tree
- Binary Tree Tilt
- Diameter of Binary Tree
- Path Sum II
- Longest Univalue Path
- Graphs Overview
- Graph Representation: Adjacency List
- Clone Graph
- Graph Valid Tree
- Matrices as Graphs
- Flood Fill
- Types of DFS (Tree Traversals)
- Number of Islands
- Surrounded Regions
- Pacific Atlantic Water FlowFree
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 16 coding interview patterns, and its problems also appear in the DSA 75 interview sprint.