type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph/matrix data structures. The algorithm starts at the root (or an arbitrary node) and explores as far as possible along each branch before backtracking. It's naturally implemented with recursion (system call stack) or with your own explicit stack.
The four canonical DFS styles
1. Pure Return-Value DFS （Recursive）
A postorder style where each call returns a value computed from the results of its required subcalls (i.e., its dependencies). No external mutable state is modified.
- Idea: For a state
S, first obtain the results of all dependent subproblemsD₁ ... Dₖvia recursive calls, then combine them to produce and returnresult(S).
- Characteristics
- Often allocates intermediate objects during combination (e.g., list concatenation), which can be slower/more memory-intensive in Python.
- Naturally expresses postorder evaluation: work happens on return after subcalls finish.
Example: LeetCode 78 Subsets
2. Side-effect Backtracking （Recursive）
This method passes state information (like the path prefix or accumulated sum) from the parent to the children. The core results are typically generated by updating a shared/global variable.
- Idea: The function's parameters carry the "prefix" information.
- Characteristic: Efficient as it avoids massive object creation; results are typically collected via a list or dictionary passed by reference, or by updating a global variable.
- Application: Tree Traversal, Level Averages, and problems requiring the root-to-current-node path value.
It is ideal for search problems involving pruning (early exit from unpromising branches), managing streaming results, and carefully controlling state changes—often requiring logic for "same-level de-dup."
Backtracking template (choose → recurse → undo)
Example: Same-level de-dup (LeetCode 90 Subsets II)
3. Generator DFS (Recursive, streaming)
For scenarios involving massive search spaces or the need for early stopping without generating all results at once, using Generators that
yield results is highly effective. Pros: Tiny peak memory (besides current path); can early-exit.
Cons: Consumers must iterate; collecting to a list forfeits the memory advantage.
4. DFS with an Explicit Stack (Iterative)
Same search order as recursive DFS, but you manage the stack.
This implementation would help void recursion limits and has deterministic control over order.
Comparison
Style | Best For | Strengths | Trade-offs |
Pure Returns | Tree DP, combining child results (heights, sizes, mins/maxes) | - Stateless recursion
- Clean aggregation of results
- Natural fit for trees | - Harder to track global state
- Less flexible for path construction |
Backtracking | Constraints, pruning, path building, prefix sums, streaming | - Fine-grained control over recursion
- Easy to prune invalid paths
- Good for stateful exploration | - Can be inefficient without pruning
- Risk of recomputation without memoization |
Generators | Massive search spaces, early stopping, lazy evaluation | - Memory-efficient
- Supports streaming
- Enables short-circuiting | - Harder to debug
- May obscure control flow |
Iterative | Deep recursion risk, team preference, system integration | - Avoids stack overflow
- Explicit control over state
- Easier to integrate with loops | - Verbose for recursive logic
- Manual stack management can be error-prone |
DFS in Tree Structures
In tree structures, Depth-First Search (DFS) explores each branch as deeply as possible before backtracking, naturally fitting recursive or stack-based traversal. It’s commonly used for tasks like traversal, collections (e.g., all paths, node lists) and aggregations (e.g., height, sums, lowest common ancestor) in hierarchical data.
DFS runs in O(N) time on a tree, where N is the number of nodes, since each node is visited exactly once. And the space complexity is O(H) for the recursion (or stack) depth, where H is the tree’s height.
Traversal
Bottom-up (return merged list)
Return and merge the recursive results of left and right subtrees.
Top-down (fill a list as you go)
Pass and update a shared list while traversing.
Path Builders
Prefer Bottom-Up When the result depends on child existence (e.g.,
path_to, all_paths).Prefer Top-Down When we need pruning or early stopping using prefix info.
Goal | Bottom-Up Strategy | Top-Down Strategy | Notes |
Path to a target node | Return the suffix path from the child when found, and prepend the current node while backtracking. | Pass a running prefix path downward and backtrack ( append / pop). | Bottom-up is simpler since each call either returns None or a full path. |
All root-to-leaf paths | Leaf returns [[root.val]];
parent prepends its own value to each child path and merges. | Use backtracking to track the path prefix and take snapshots at leaves. | Usually bottom-up is cleaner for static path enumeration. |
Path to target
All root-to-leaf paths
Metrics & Aggregation
Goal | Bottom-Up Formula / Logic | Key Base Case / Note |
Tree height | 1 + max(left_height, right_height) | Return -1 for empty tree (height as edge count) or 0 if counting nodes. |
Tree minimum value | min(root.val, left_min, right_min) | Return +inf for empty subtree. |
Maximum root-to-leaf path sum | root.val + max(left_sum, right_sum) | Return root.val directly at a leaf; return -inf for empty branch. |
Lowest Common Ancestor (LCA) | Recurse left/right;
if both non-null, current node is LCA. Otherwise return non-null child. | Works for general binary trees, not just BSTs. |
Tree height
Min value
Max root→leaf sum
Lowest Common Ancestor
DFS in Graphs / Matrices
Depth-First Search (DFS) explores as far as possible along each branch before backtracking, making it ideal for tasks like connected component detection, cycle checking, and pathfinding in graphs or matrices. In grid-based problems, DFS can be implemented recursively or iteratively to traverse adjacent cells, often using visited flags or boundary checks to avoid revisiting.
In general Graphs or Matrices (which can be viewed as grids/graphs), the use of a
visited set is crucial to avoid infinite loops (cycles) and redundant work. Specifically, creates a cycle. Without tracking visited nodes, DFS would endlessly loop between A and B. And if multiple paths lead to the same node (e.g., A→C and B → C), visited ensures node C and its subtree are explored only once.Its performance is highly efficient on graphs, achieving a time complexity of O(V + E) for visiting all vertices (V) and edges (E) once. And it requires space complexity of O(V) for the stack and the required
visited structure; General Graph DFS Template
Graph Application Examples
Goal | Method | Core Logic |
Connected Components | Top-Down | Outer loop iterates all nodes.
DFS ( explore) simply marks all reachable nodes as visited.
Outer loop increments a counter for each successful explore. |
Component Size | Bottom-Up | DFS ( explore_size) returns a numerical size.
size = 1 + sum(explore_size(neighbor)) |
Island Count (Matrix) | Top-Down | Outer loop iterates grid cells.
DFS marks connected land cells ( L) as visited and returns True if a new island is found. |
Example: Reachability between nodes
Example: Largest Component Size
Directed Graph Cycle Detection (Three-Color Marking)
To detect cycles in directed graphs, we need more than a simple
visited set. We use the Three-Color Marking technique to track nodes within the current recursion path.
Color | State (Set) | Purpose |
White | Not in any set. | Unvisited. |
Grey | visiting | Currently in the recursion stack (part of the current path). |
Black | visited | Fully explored (all descendants processed). |
Cycle Condition: If the search encounters a Grey node, a cycle exists.
Endnote
Depth-First Search (DFS) is a power tool for deep exploration and fundamental traversal strategy that explores as far as possible along each branch before backtracking. It can be implemented recursively or iteratively with an explicit stack, making it flexible for trees, graphs, and matrices.
- Author:Fan Luo
- URL:https://fanluo.me/article/depth-first-search-exploring-deep-before-wide
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
Implementing Efficient Prefix Search with Tries
下一篇
Breadth-First Search: Level-Order Exploration