🎯 DFS Basics
1️⃣ Core Framework
When discussing DFS Basics, I frame it as:
- What problem pattern DFS solves
- Recursive DFS vs iterative DFS
- DFS on binary trees
- DFS on graphs
- Visited set
- DFS on grids
- Connected components
- Backtracking relationship
- Common edge cases
- Senior-level explanation
2️⃣ What Problem Are We Solving?
DFS, or Depth-First Search, is used when we need to explore as deep as possible before backtracking.
It is commonly used for:
- Tree traversal
- Graph traversal
- Connected components
- Path existence
- Cycle detection
- Backtracking
- Grid traversal
- Topological sort
- Recursion-based exploration
- Exhaustive search
The core idea is:
Go deep first.
When there is no further path,
backtrack and explore another branch.
👉 Interview Answer
DFS is a traversal algorithm that explores one path as deeply as possible before backtracking.
It is useful for trees, graphs, grids, connected components, path existence, and backtracking problems.
DFS can be implemented recursively using the call stack or iteratively using an explicit stack.
3️⃣ Why DFS Works
Depth-First Behavior
Suppose we start from node A.
A
├── B
│ ├── D
│ └── E
└── C
DFS may visit:
A → B → D → E → C
It goes deep into one branch before moving to the next branch.
Recursive Nature
DFS maps naturally to recursion:
process current node
then recursively process each neighbor or child
Key Idea
DFS keeps exploring until it hits:
null
visited node
boundary
obstacle
target
base case
Then it returns to the previous call.
👉 Interview Answer
DFS works because many structures are naturally recursive.
For each node, we process it and then recursively explore its children or neighbors.
When a path ends, the recursion returns and DFS continues exploring the next branch.
4️⃣ DFS vs BFS
DFS
Uses:
recursion or stack
Traversal order:
depth first
Best for:
path existence
connected components
backtracking
cycle detection
tree recursion
topological sort
BFS
Uses:
queue
Traversal order:
level by level
Best for:
shortest path in unweighted graph
minimum steps
level-order traversal
nearest target
multi-source expansion
Comparison
| Pattern | Data Structure | Traversal Order | Best For |
|---|---|---|---|
| DFS | Stack / Recursion | Deep first | Backtracking, components, path existence |
| BFS | Queue | Level by level | Shortest path, minimum steps |
👉 Interview Answer
DFS explores deeply first using recursion or a stack.
BFS explores level by level using a queue.
If the problem asks for shortest path or minimum steps in an unweighted graph, BFS is usually better.
If the problem asks to explore all possibilities, detect components, or use recursion naturally, DFS is usually better.
5️⃣ Recursive DFS Template
Graph DFS Template
def dfs(node, graph, visited):
if node in visited:
return
visited.add(node)
for neighbor in graph[node]:
dfs(neighbor, graph, visited)
Key Components
Recursive DFS usually needs:
- Current node or state
- Base case
- Visited set if graph can cycle
- Neighbor generation
- Recursive calls
👉 Interview Answer
Recursive DFS processes the current node and then recursively explores its neighbors.
If the graph may contain cycles, I use a visited set.
The visited set prevents infinite recursion and duplicate work.
6️⃣ Iterative DFS Template
Why Use Iterative DFS?
Recursive DFS is simple, but recursion depth may be a problem.
Iterative DFS uses an explicit stack.
Code
def dfs_iterative(start, graph):
stack = [start]
visited = set([start])
order = []
while stack:
node = stack.pop()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)
return order
Stack Behavior
Last In, First Out
The most recently added node is processed first.
👉 Interview Answer
DFS can be implemented iteratively with a stack.
The stack stores nodes that still need to be explored.
This avoids recursion depth issues and gives more explicit control over traversal order.
7️⃣ DFS on Binary Tree
Common Tree DFS Orders
For binary trees, DFS has three common orders:
preorder: root → left → right
inorder: left → root → right
postorder: left → right → root
Preorder Traversal
def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
Inorder Traversal
def inorder(root):
if not root:
return []
return inorder(root.left) + [root.val] + inorder(root.right)
Postorder Traversal
def postorder(root):
if not root:
return []
return postorder(root.left) + postorder(root.right) + [root.val]
👉 Interview Answer
For binary tree DFS, the traversal order depends on when we process the root.
Preorder processes root before children.
Inorder processes root between left and right.
Postorder processes root after children.
These are all DFS traversals.
8️⃣ Binary Tree Maximum Depth
Problem
Find the maximum depth of a binary tree.
Code
def max_depth(root):
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return 1 + max(left_depth, right_depth)
Why DFS Works
The maximum depth of a tree is:
1 + max(left subtree depth, right subtree depth)
This is a recursive definition.
👉 Interview Answer
Maximum depth is naturally solved by DFS.
The depth of a node is one plus the maximum depth of its left and right subtrees.
The base case is a null node, which has depth zero.
9️⃣ Path Sum
Problem
Determine whether a root-to-leaf path has sum equal to target.
Code
def has_path_sum(root, target_sum):
if not root:
return False
if not root.left and not root.right:
return target_sum == root.val
remaining = target_sum - root.val
return (
has_path_sum(root.left, remaining)
or
has_path_sum(root.right, remaining)
)
Key Insight
DFS carries state along the path:
remaining sum
At each node:
remaining = remaining - current value
👉 Interview Answer
Path Sum is a DFS problem because we need to explore root-to-leaf paths.
I carry the remaining target sum during recursion.
When I reach a leaf node, I check whether the remaining sum equals the leaf value.
🔟 DFS on Graph
Graph Representation
Adjacency list:
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "E"],
"D": ["B"],
"E": ["C"]
}
Code
def graph_dfs(graph, start):
visited = set()
order = []
def dfs(node):
if node in visited:
return
visited.add(node)
order.append(node)
for neighbor in graph[node]:
dfs(neighbor)
dfs(start)
return order
Why Visited Is Required
Graphs may contain cycles.
Example:
A ↔ B
Without visited:
A calls B
B calls A
A calls B again
...
This causes infinite recursion.
👉 Interview Answer
For graph DFS, I use a visited set because graphs may contain cycles.
I mark a node as visited before exploring its neighbors.
This prevents infinite recursion and ensures each node is processed once.
1️⃣1️⃣ Connected Components
Problem
Given an undirected graph, count the number of connected components.
Code
def count_components(n, edges):
graph = {i: [] for i in range(n)}
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
visited = set()
components = 0
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
for node in range(n):
if node not in visited:
components += 1
dfs(node)
return components
Key Insight
Each DFS starting from an unvisited node visits one full component.
👉 Interview Answer
To count connected components, I iterate through all nodes.
When I find an unvisited node, I start a DFS from it.
That DFS visits the entire connected component.
Therefore, each new DFS call represents one component.
1️⃣2️⃣ Number of Islands
Problem
Count connected groups of "1" cells in a grid.
Code
def num_islands(grid):
if not grid or not grid[0]:
return 0
rows = len(grid)
cols = len(grid[0])
islands = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if grid[r][c] != "1":
return
grid[r][c] = "0"
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
islands += 1
dfs(r, c)
return islands
Key Insight
Each DFS consumes one entire island.
Find a land cell
count one island
DFS marks all connected land as visited
👉 Interview Answer
Number of Islands is a connected-component problem on a grid.
Each land cell is a node.
When I find an unvisited land cell, I count one island and use DFS to mark all connected land cells.
This prevents counting the same island multiple times.
1️⃣3️⃣ Grid DFS Template
Template
def grid_dfs(grid, r, c):
rows = len(grid)
cols = len(grid[0])
def dfs(row, col):
if row < 0 or row >= rows or col < 0 or col >= cols:
return
if grid[row][col] == "#":
return
if grid[row][col] == "visited":
return
grid[row][col] = "visited"
dfs(row + 1, col)
dfs(row - 1, col)
dfs(row, col + 1)
dfs(row, col - 1)
dfs(r, c)
Direction Array Version
def grid_dfs_with_directions(grid, r, c):
rows = len(grid)
cols = len(grid[0])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def dfs(row, col):
if row < 0 or row >= rows or col < 0 or col >= cols:
return
if grid[row][col] != "1":
return
grid[row][col] = "0"
for dr, dc in directions:
dfs(row + dr, col + dc)
dfs(r, c)
👉 Interview Answer
For grid DFS, I treat each cell as a graph node.
Neighbor generation comes from moving up, down, left, and right.
The base cases are boundary check, obstacle check, and visited check.
1️⃣4️⃣ Flood Fill
Problem
Change the color of a connected region starting from a given cell.
Code
def flood_fill(image, sr, sc, color):
rows = len(image)
cols = len(image[0])
original = image[sr][sc]
if original == color:
return image
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if image[r][c] != original:
return
image[r][c] = color
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
dfs(sr, sc)
return image
Important Edge Case
If the original color equals the new color:
original == color
Return immediately.
Otherwise DFS may revisit forever if using color as visited marker.
👉 Interview Answer
Flood Fill is a DFS connected-region problem.
I store the original color, then recursively visit all neighboring cells with the same original color.
Each visited cell is changed to the new color.
If the original color already equals the new color, I return immediately to avoid infinite recursion.
1️⃣5️⃣ Cycle Detection With DFS
Undirected Graph
In an undirected graph, a cycle exists if we visit an already visited neighbor that is not the parent.
Code
def has_cycle_undirected(n, edges):
graph = {i: [] for i in range(n)}
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
visited = set()
def dfs(node, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor == parent:
continue
if neighbor in visited:
return True
if dfs(neighbor, node):
return True
return False
for node in range(n):
if node not in visited:
if dfs(node, -1):
return True
return False
👉 Interview Answer
In an undirected graph, I use DFS with a parent parameter.
If I see a visited neighbor that is not the parent, then I found a cycle.
The parent check is necessary because every undirected edge appears in both directions.
1️⃣6️⃣ Directed Graph Cycle Detection
Key Idea
For directed graphs, we track node states:
0 = unvisited
1 = visiting
2 = visited
If DFS reaches a node that is currently visiting:
cycle exists
Code
def has_cycle_directed(n, edges):
graph = {i: [] for i in range(n)}
for a, b in edges:
graph[a].append(b)
state = [0] * n
def dfs(node):
if state[node] == 1:
return True
if state[node] == 2:
return False
state[node] = 1
for neighbor in graph[node]:
if dfs(neighbor):
return True
state[node] = 2
return False
for node in range(n):
if state[node] == 0:
if dfs(node):
return True
return False
👉 Interview Answer
For directed graph cycle detection, I use three states: unvisited, visiting, and visited.
If DFS reaches a visiting node, that means there is a back edge, so a cycle exists.
Once all neighbors are processed, I mark the node as fully visited.
1️⃣7️⃣ Course Schedule
Problem
Given course prerequisites, determine whether all courses can be finished.
This is directed graph cycle detection.
a depends on b
b depends on c
c depends on a
cycle → impossible
Code
def can_finish(num_courses, prerequisites):
graph = {i: [] for i in range(num_courses)}
for course, prereq in prerequisites:
graph[prereq].append(course)
state = [0] * num_courses
def dfs(course):
if state[course] == 1:
return False
if state[course] == 2:
return True
state[course] = 1
for next_course in graph[course]:
if not dfs(next_course):
return False
state[course] = 2
return True
for course in range(num_courses):
if state[course] == 0:
if not dfs(course):
return False
return True
👉 Interview Answer
Course Schedule is a directed graph cycle detection problem.
Each course is a node, and each prerequisite relation is a directed edge.
If there is a cycle, then some courses depend on each other and cannot be completed.
I use DFS with three states to detect cycles.
1️⃣8️⃣ DFS and Backtracking
Relationship
Backtracking is a special form of DFS.
DFS explores paths.
Backtracking explores candidate choices and undoes choices.
Pattern
choose
explore
unchoose
Template
def backtrack(path, choices):
if is_solution(path):
result.append(path[:])
return
for choice in choices:
if not valid(choice):
continue
path.append(choice)
backtrack(path, next_choices)
path.pop()
👉 Interview Answer
Backtracking is DFS over a decision tree.
Each recursive call represents a choice.
We choose an option, recursively explore deeper, and then undo the choice before trying the next option.
This is why backtracking is often described as choose, explore, unchoose.
1️⃣9️⃣ DFS With Return Values
Sometimes DFS Returns Information
Examples:
tree height
subtree size
max path sum
whether subtree is valid
whether target exists
Example: Balanced Binary Tree
def is_balanced(root):
def height(node):
if not node:
return 0
left = height(node.left)
if left == -1:
return -1
right = height(node.right)
if right == -1:
return -1
if abs(left - right) > 1:
return -1
return 1 + max(left, right)
return height(root) != -1
Key Insight
DFS can either:
perform traversal side effects
or
return computed information upward
👉 Interview Answer
DFS is not only for traversal.
It can also return information from children to parent.
For tree problems, this bottom-up DFS pattern is very common.
Each recursive call computes information about a subtree and returns it upward.
2️⃣0️⃣ DFS Complexity Analysis
Tree DFS
For n nodes:
Time: O(n)
Space: O(h)
Where h is tree height.
Worst case:
O(n)
for a skewed tree.
Best balanced case:
O(log n)
recursion stack depth.
Graph DFS
For graph with V vertices and E edges:
Time: O(V + E)
Space: O(V)
Grid DFS
For m x n grid:
Time: O(mn)
Space: O(mn)
Worst-case recursion depth can be all cells.
👉 Interview Answer
DFS visits each node or cell at most once, so the time complexity is usually O(n) for trees, O(V + E) for graphs, and O(mn) for grids.
Space complexity comes from recursion depth or explicit stack.
For a balanced tree, recursion depth is O(log n), but for a skewed tree or large grid, it can be O(n).
2️⃣1️⃣ Common Edge Cases
Empty Input
root = None
grid = []
graph = {}
Single Node
root only
one graph node
one grid cell
Cycles in Graph
Need visited set.
Disconnected Graph
Need to iterate over all nodes.
Recursion Depth
Large input may cause recursion depth issues.
Mutating Input
Some DFS marks visited by modifying input.
Make sure this is allowed.
👉 Interview Answer
Common DFS edge cases include empty input, single node, graph cycles, disconnected graphs, recursion depth limits, and whether modifying the input is allowed.
For graphs, I use visited.
For disconnected graphs, I start DFS from every unvisited node.
2️⃣2️⃣ Common Mistakes
Mistake 1: Forgetting Base Case
Without base case, recursion may never stop.
Mistake 2: Forgetting Visited in Graphs
This causes infinite recursion in cyclic graphs.
Mistake 3: Marking Visited Too Late
Usually mark before recursive calls.
visited.add(node)
Mistake 4: Not Handling Disconnected Graph
Starting DFS from only one node may miss other components.
Mistake 5: Confusing DFS With Backtracking
DFS explores graph or tree structure.
Backtracking explores decision choices and must undo state.
Mistake 6: Recursion Limit
In Python, deep recursion can fail.
Use iterative DFS if needed.
👉 Interview Answer
Common DFS mistakes include missing base cases, forgetting visited sets, marking visited too late, ignoring disconnected components, confusing DFS with backtracking, and not considering recursion depth limits.
I avoid these by defining the base case, visited logic, and traversal scope before coding.
2️⃣3️⃣ When DFS Applies
Good Fit
Use DFS when the problem asks for:
path existence
connected components
explore all possibilities
tree recursion
grid region traversal
cycle detection
backtracking
topological exploration
subtree information
Problem Signals
Look for words like:
all paths
exists path
connected
island
component
cycle
recursive
subtree
valid tree
backtracking
permutations
combinations
👉 Interview Answer
I consider DFS when the problem requires deep exploration, connected component detection, path existence, cycle detection, tree recursion, or backtracking.
DFS is especially natural when the problem can be expressed recursively.
2️⃣4️⃣ When DFS Does Not Apply
Not Good Fit
DFS may not be ideal when:
need shortest path in unweighted graph
need minimum number of moves
need level-order traversal
need nearest target
large recursion depth risk
Better Alternatives
| Problem Type | Better Pattern |
|---|---|
| Shortest path unweighted | BFS |
| Weighted shortest path | Dijkstra |
| Level-order traversal | BFS |
| Nearest source distance | Multi-source BFS |
| Very deep recursion | Iterative DFS / BFS |
| Optimization with overlapping subproblems | Dynamic Programming |
👉 Interview Answer
DFS is not always the right traversal.
If the problem asks for shortest path or minimum steps in an unweighted graph, BFS is usually better because it explores level by level.
If recursion depth is too large, iterative DFS or BFS may be safer.
2️⃣5️⃣ Standard Templates
Tree DFS Template
def dfs(root):
if not root:
return
# process root
dfs(root.left)
dfs(root.right)
Tree DFS With Return Value
def dfs(root):
if not root:
return base_value
left = dfs(root.left)
right = dfs(root.right)
return combine(root, left, right)
Graph DFS Template
def dfs(node):
if node in visited:
return
visited.add(node)
for neighbor in graph[node]:
dfs(neighbor)
Grid DFS Template
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if grid[r][c] != target_value:
return
grid[r][c] = visited_value
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
Iterative DFS Template
def dfs_iterative(start):
stack = [start]
visited = set([start])
while stack:
node = stack.pop()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)
Directed Graph Cycle Detection Template
def has_cycle(graph, n):
state = [0] * n
def dfs(node):
if state[node] == 1:
return True
if state[node] == 2:
return False
state[node] = 1
for neighbor in graph[node]:
if dfs(neighbor):
return True
state[node] = 2
return False
for node in range(n):
if state[node] == 0:
if dfs(node):
return True
return False
🧠 Staff-Level Answer Final
👉 Interview Answer Full Version
DFS, or Depth-First Search, is a traversal algorithm that explores one branch as deeply as possible before backtracking.
It can be implemented recursively using the call stack or iteratively using an explicit stack.
DFS is especially useful for tree traversal, graph traversal, connected components, path existence, cycle detection, grid region traversal, and backtracking problems.
In tree problems, DFS maps naturally to recursion. For each node, we process the node and recursively process its left and right children. Depending on when we process the root, we get preorder, inorder, or postorder traversal.
DFS can also return information from children to parent. For example, maximum depth returns one plus the maximum depth of the left and right subtrees. Balanced tree checking returns subtree height and can propagate failure upward.
In graph problems, DFS requires a visited set because graphs may contain cycles. I usually mark a node as visited before exploring neighbors, which prevents infinite recursion and duplicate work.
For disconnected graphs, I iterate through all nodes and start DFS from every unvisited node. Each DFS call visits one connected component.
In grid problems, each cell can be treated as a graph node. The base cases are boundary checks, obstacle checks, and visited checks. Number of Islands and Flood Fill are classic examples.
DFS is also used for cycle detection. In undirected graphs, we track the parent node and detect a cycle when we visit an already visited neighbor that is not the parent. In directed graphs, we use three states: unvisited, visiting, and visited. Reaching a visiting node means there is a cycle.
Backtracking is a special form of DFS over a decision tree. It follows the pattern choose, explore, unchoose. This is used for permutations, combinations, subsets, and many search problems.
The complexity of DFS is usually O(n) for trees, O(V + E) for graphs, and O(mn) for grids. Space complexity depends on recursion depth or explicit stack size.
At a senior level, I would explain: what the node or state is, what the base case is, how neighbors are generated, how visited is tracked, whether the graph may be disconnected, and whether DFS should return information upward or only perform traversal.
⭐ Final Insight
DFS 的核心不是“递归调用”。
它的核心是 deep exploration plus backtracking。
Senior-level 的重点是：
node/state 是什么， base case 是什么， visited 何时标记， neighbor 如何生成， 是否需要处理 disconnected components， 以及 DFS 是单纯 traversal，还是需要 return information upward。
能讲清楚这些， DFS 就不仅是递归模板， 而是一种处理 tree、graph、grid、cycle detection 和 backtracking 的通用搜索模型。
中文部分
🎯 DFS Basics
1️⃣ 核心框架
讨论 DFS Basics 时，我通常从：
- DFS 解决什么问题
- Recursive DFS vs iterative DFS
- Binary tree 上的 DFS
- Graph 上的 DFS
- Visited set
- Grid 上的 DFS
- Connected components
- Backtracking 的关系
- 常见 edge cases
- 高级工程师解释方式
2️⃣ 要解决什么问题？
DFS，也就是 Depth-First Search，用于先向深处探索。
它常用于：
- Tree traversal
- Graph traversal
- Connected components
- Path existence
- Cycle detection
- Backtracking
- Grid traversal
- Topological sort
- Recursion-based exploration
- Exhaustive search
核心思想是：
先沿着一条路径走到底。
走不下去了，再回退，
然后探索另一个分支。
👉 面试回答
DFS 是一种 traversal algorithm。
它会先沿着一条 path 尽可能深入探索， 然后再 backtrack。
DFS 常用于 trees、graphs、grids、connected components、path existence 和 backtracking 问题。
DFS 可以用 recursion 实现， 也可以用 explicit stack 实现。
3️⃣ 为什么 DFS 有效？
Depth-First 行为
假设从 node A 开始：
A
├── B
│ ├── D
│ └── E
└── C
DFS 可能访问：
A → B → D → E → C
它会先深入一个 branch，再探索下一个 branch。
Recursive Nature
DFS 很自然地对应 recursion：
process current node
then recursively process each neighbor or child
Key Idea
DFS 会一直探索，直到遇到：
null
visited node
boundary
obstacle
target
base case
然后返回上一层调用。
👉 面试回答
DFS 有效，是因为很多结构天然是 recursive 的。
对每个 node， 我们处理当前 node， 然后递归探索它的 children 或 neighbors。
当一条 path 走到尽头时， recursion 返回， DFS 继续探索其他 branches。
4️⃣ DFS vs BFS
DFS
使用：
recursion or stack
遍历顺序：
depth first
适合：
path existence
connected components
backtracking
cycle detection
tree recursion
topological sort
BFS
使用：
queue
遍历顺序：
level by level
适合：
shortest path in unweighted graph
minimum steps
level-order traversal
nearest target
multi-source expansion
Comparison
| Pattern | Data Structure | Traversal Order | Best For |
|---|---|---|---|
| DFS | Stack / Recursion | Deep first | Backtracking, components, path existence |
| BFS | Queue | Level by level | Shortest path, minimum steps |
👉 面试回答
DFS 使用 recursion 或 stack， 先向深处探索。
BFS 使用 queue， 按层探索。
如果题目问 unweighted graph 中的 shortest path 或 minimum steps， BFS 通常更合适。
如果题目问探索所有可能性、connected components， 或者问题本身很适合递归， DFS 通常更自然。
5️⃣ Recursive DFS Template
Graph DFS Template
def dfs(node, graph, visited):
if node in visited:
return
visited.add(node)
for neighbor in graph[node]:
dfs(neighbor, graph, visited)
Key Components
Recursive DFS 通常需要：
- Current node or state
- Base case
- Visited set if graph can cycle
- Neighbor generation
- Recursive calls
👉 面试回答
Recursive DFS 会处理当前 node， 然后递归探索它的 neighbors。
如果 graph 可能有 cycle， 我会使用 visited set。
Visited set 可以防止 infinite recursion 和 duplicate work。
6️⃣ Iterative DFS Template
为什么用 Iterative DFS？
Recursive DFS 简洁， 但 recursion depth 可能是问题。
Iterative DFS 使用 explicit stack。
Code
def dfs_iterative(start, graph):
stack = [start]
visited = set([start])
order = []
while stack:
node = stack.pop()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)
return order
Stack Behavior
Last In, First Out
最近加入的 node 会最先被处理。
👉 面试回答
DFS 可以用 explicit stack 迭代实现。
Stack 存储之后还需要探索的 nodes。
这种写法可以避免 recursion depth 问题， 也能让 traversal order 更可控。
7️⃣ Binary Tree DFS
常见 Tree DFS 顺序
Binary tree 中，DFS 有三种常见顺序：
preorder: root → left → right
inorder: left → root → right
postorder: left → right → root
Preorder Traversal
def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
Inorder Traversal
def inorder(root):
if not root:
return []
return inorder(root.left) + [root.val] + inorder(root.right)
Postorder Traversal
def postorder(root):
if not root:
return []
return postorder(root.left) + postorder(root.right) + [root.val]
👉 面试回答
对 binary tree DFS， traversal order 取决于什么时候 process root。
Preorder 是先 root，再 children。
Inorder 是 left、root、right。
Postorder 是 children 后 root。
它们本质上都是 DFS。
8️⃣ Binary Tree Maximum Depth
Problem
找到 binary tree 的最大深度。
Code
def max_depth(root):
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return 1 + max(left_depth, right_depth)
为什么 DFS 合适？
Tree 的 maximum depth 可以递归定义为：
1 + max(left subtree depth, right subtree depth)
👉 面试回答
Maximum depth 很适合 DFS。
一个 node 的 depth 等于： 1 + 左右子树最大 depth。
Base case 是 null node， 它的 depth 是 0。
9️⃣ Path Sum
Problem
判断是否存在 root-to-leaf path， 使路径 sum 等于 target。
Code
def has_path_sum(root, target_sum):
if not root:
return False
if not root.left and not root.right:
return target_sum == root.val
remaining = target_sum - root.val
return (
has_path_sum(root.left, remaining)
or
has_path_sum(root.right, remaining)
)
Key Insight
DFS 沿 path 携带 state：
remaining sum
每到一个 node：
remaining = remaining - current value
👉 面试回答
Path Sum 是 DFS 问题， 因为我们需要探索 root-to-leaf paths。
我在 recursion 中携带 remaining target sum。
当到达 leaf node 时， 检查 remaining sum 是否等于 leaf value。
🔟 Graph DFS
Graph Representation
Adjacency list:
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "E"],
"D": ["B"],
"E": ["C"]
}
Code
def graph_dfs(graph, start):
visited = set()
order = []
def dfs(node):
if node in visited:
return
visited.add(node)
order.append(node)
for neighbor in graph[node]:
dfs(neighbor)
dfs(start)
return order
为什么需要 Visited？
Graph 可能有 cycle。
Example:
A ↔ B
如果没有 visited：
A calls B
B calls A
A calls B again
...
会造成 infinite recursion。
👉 面试回答
对 graph DFS， 我会使用 visited set， 因为 graph 可能有 cycle。
我在探索 neighbors 之前先 mark visited。
这样可以避免 infinite recursion， 并保证每个 node 只处理一次。
1️⃣1️⃣ Connected Components
Problem
给定 undirected graph， 统计 connected components 数量。
Code
def count_components(n, edges):
graph = {i: [] for i in range(n)}
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
visited = set()
components = 0
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
for node in range(n):
if node not in visited:
components += 1
dfs(node)
return components
Key Insight
每次从 unvisited node 开始的 DFS， 都会访问一个完整 connected component。
👉 面试回答
统计 connected components 时， 我会遍历所有 nodes。
每当发现一个 unvisited node， 就从它开始 DFS。
这次 DFS 会访问完整的 connected component。
所以每启动一次新的 DFS， 就代表发现一个新的 component。
1️⃣2️⃣ Number of Islands
Problem
统计 grid 中 "1" 组成的 connected groups。
Code
def num_islands(grid):
if not grid or not grid[0]:
return 0
rows = len(grid)
cols = len(grid[0])
islands = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if grid[r][c] != "1":
return
grid[r][c] = "0"
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
islands += 1
dfs(r, c)
return islands
Key Insight
每次 DFS 消耗掉一个完整 island。
发现一个 land cell
count one island
DFS mark 所有 connected land visited
👉 面试回答
Number of Islands 是 grid 上的 connected-component 问题。
每个 land cell 可以看成一个 node。
当我发现一个 unvisited land cell， 就 count 一个 island， 然后用 DFS 标记所有相连的 land cells。
这样可以避免重复统计同一个 island。
1️⃣3️⃣ Grid DFS Template
Template
def grid_dfs(grid, r, c):
rows = len(grid)
cols = len(grid[0])
def dfs(row, col):
if row < 0 or row >= rows or col < 0 or col >= cols:
return
if grid[row][col] == "#":
return
if grid[row][col] == "visited":
return
grid[row][col] = "visited"
dfs(row + 1, col)
dfs(row - 1, col)
dfs(row, col + 1)
dfs(row, col - 1)
dfs(r, c)
Direction Array Version
def grid_dfs_with_directions(grid, r, c):
rows = len(grid)
cols = len(grid[0])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def dfs(row, col):
if row < 0 or row >= rows or col < 0 or col >= cols:
return
if grid[row][col] != "1":
return
grid[row][col] = "0"
for dr, dc in directions:
dfs(row + dr, col + dc)
dfs(r, c)
👉 面试回答
对 grid DFS， 我把每个 cell 当成 graph node。
Neighbor generation 来自上下左右移动。
Base cases 包括 boundary check、obstacle check 和 visited check。
1️⃣4️⃣ Flood Fill
Problem
从给定 cell 开始， 改变一个 connected region 的颜色。
Code
def flood_fill(image, sr, sc, color):
rows = len(image)
cols = len(image[0])
original = image[sr][sc]
if original == color:
return image
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if image[r][c] != original:
return
image[r][c] = color
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
dfs(sr, sc)
return image
Important Edge Case
如果 original color 等于 new color：
original == color
需要直接 return。
否则如果用 color 作为 visited marker， 可能会重复访问。
👉 面试回答
Flood Fill 是 connected-region DFS。
我先记录 original color。
然后递归访问所有相邻且颜色等于 original 的 cells。
每个访问过的 cell 都改成 new color。
如果 original color 已经等于 new color， 我会直接返回，避免重复递归。
1️⃣5️⃣ Undirected Graph Cycle Detection
Key Idea
在 undirected graph 中， 如果访问到一个已经 visited 的 neighbor， 并且它不是 parent， 说明存在 cycle。
Code
def has_cycle_undirected(n, edges):
graph = {i: [] for i in range(n)}
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
visited = set()
def dfs(node, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor == parent:
continue
if neighbor in visited:
return True
if dfs(neighbor, node):
return True
return False
for node in range(n):
if node not in visited:
if dfs(node, -1):
return True
return False
👉 面试回答
在 undirected graph 中检测 cycle， 我会在 DFS 中携带 parent。
如果遇到一个 visited neighbor， 且这个 neighbor 不是 parent， 说明发现了 cycle。
Parent check 很重要， 因为 undirected edge 会双向出现。
1️⃣6️⃣ Directed Graph Cycle Detection
Key Idea
Directed graph 中，使用三种状态：
0 = unvisited
1 = visiting
2 = visited
如果 DFS 遇到 visiting node：
cycle exists
Code
def has_cycle_directed(n, edges):
graph = {i: [] for i in range(n)}
for a, b in edges:
graph[a].append(b)
state = [0] * n
def dfs(node):
if state[node] == 1:
return True
if state[node] == 2:
return False
state[node] = 1
for neighbor in graph[node]:
if dfs(neighbor):
return True
state[node] = 2
return False
for node in range(n):
if state[node] == 0:
if dfs(node):
return True
return False
👉 面试回答
Directed graph cycle detection 通常用三色 DFS。
0 表示 unvisited。
1 表示 visiting，也就是当前 recursion stack 中。
2 表示 visited，说明这个 node 的所有后续路径已经处理完。
如果 DFS 遇到 state 为 visiting 的 node， 说明存在 back edge，也就是 cycle。
1️⃣7️⃣ Course Schedule
Problem
给定 course prerequisites， 判断是否能完成所有课程。
这本质是 directed graph cycle detection。
a depends on b
b depends on c
c depends on a
cycle → impossible
Code
def can_finish(num_courses, prerequisites):
graph = {i: [] for i in range(num_courses)}
for course, prereq in prerequisites:
graph[prereq].append(course)
state = [0] * num_courses
def dfs(course):
if state[course] == 1:
return False
if state[course] == 2:
return True
state[course] = 1
for next_course in graph[course]:
if not dfs(next_course):
return False
state[course] = 2
return True
for course in range(num_courses):
if state[course] == 0:
if not dfs(course):
return False
return True
👉 面试回答
Course Schedule 是 directed graph cycle detection。
每门课是一个 node。
Prerequisite relation 是 directed edge。
如果图中存在 cycle， 说明课程之间互相依赖， 无法完成所有课程。
我会用三色 DFS 检测 cycle。
1️⃣8️⃣ DFS 和 Backtracking
Relationship
Backtracking 是 DFS 的一种特殊形式。
DFS 探索路径。
Backtracking 探索 choices，并且要 undo choice。
Pattern
choose
explore
unchoose
Template
def backtrack(path, choices):
if is_solution(path):
result.append(path[:])
return
for choice in choices:
if not valid(choice):
continue
path.append(choice)
backtrack(path, next_choices)
path.pop()
👉 面试回答
Backtracking 可以看成 decision tree 上的 DFS。
每一层 recursion 代表一个 choice。
我们先 choose 一个选择， 然后递归 explore， 最后 undo 这个选择， 再尝试下一个选择。
所以 backtracking 常被总结为 choose、explore、unchoose。
1️⃣9️⃣ DFS With Return Values
DFS 有时需要返回信息
Examples:
tree height
subtree size
max path sum
whether subtree is valid
whether target exists
Example: Balanced Binary Tree
def is_balanced(root):
def height(node):
if not node:
return 0
left = height(node.left)
if left == -1:
return -1
right = height(node.right)
if right == -1:
return -1
if abs(left - right) > 1:
return -1
return 1 + max(left, right)
return height(root) != -1
Key Insight
DFS 可以：
perform traversal side effects
or
return computed information upward
👉 面试回答
DFS 不只是 traversal。
它也可以从 child 向 parent 返回信息。
对 tree problems 来说， 这种 bottom-up DFS 很常见。
每个 recursive call 计算一个 subtree 的信息， 然后把结果返回给 parent。
2️⃣0️⃣ DFS Complexity Analysis
Tree DFS
对于 n 个 nodes：
Time: O(n)
Space: O(h)
h 是 tree height。
Worst case:
O(n)
如果 tree 是 skewed。
Balanced tree:
O(log n)
recursion stack depth。
Graph DFS
对于 V 个 vertices 和 E 条 edges：
Time: O(V + E)
Space: O(V)
Grid DFS
对于 m x n grid：
Time: O(mn)
Space: O(mn)
Worst-case recursion depth 可能是所有 cells。
👉 面试回答
DFS 通常每个 node 或 cell 访问一次。
所以 tree DFS 是 O(n)， graph DFS 是 O(V + E)， grid DFS 是 O(mn)。
Space complexity 来自 recursion depth 或 explicit stack。
对 balanced tree，recursion depth 是 O(log n)。
对 skewed tree 或大 grid，worst case 可能是 O(n)。
2️⃣1️⃣ 常见 Edge Cases
Empty Input
root = None
grid = []
graph = {}
Single Node
root only
one graph node
one grid cell
Graph Cycles
需要 visited set。
Disconnected Graph
需要遍历所有 nodes。
Recursion Depth
大输入可能导致 recursion depth issue。
Mutating Input
有些 DFS 会修改 input 来 mark visited。
要确认题目是否允许。
👉 面试回答
DFS 常见 edge cases 包括 empty input、 single node、 graph cycles、 disconnected graph、 recursion depth limit， 以及是否允许修改 input。
对 graph，我会使用 visited。
对 disconnected graph，我会从每个 unvisited node 启动 DFS。
2️⃣2️⃣ 常见错误
Mistake 1: 忘记 Base Case
没有 base case，recursion 可能永远不会停止。
Mistake 2: Graph 中忘记 Visited
Cyclic graph 中会造成 infinite recursion。
Mistake 3: Mark Visited 太晚
通常应该在 recursive calls 之前 mark。
visited.add(node)
Mistake 4: 没处理 Disconnected Graph
只从一个 node 开始 DFS， 可能漏掉其他 components。
Mistake 5: 混淆 DFS 和 Backtracking
DFS 探索 graph/tree structure。
Backtracking 探索 decision choices， 并且需要 undo state。
Mistake 6: Recursion Limit
Python 中深递归可能失败。
必要时使用 iterative DFS。
👉 面试回答
DFS 常见错误包括： 忘记 base case、 graph 中忘记 visited、 visited mark 太晚、 没处理 disconnected components、 混淆 DFS 和 backtracking、 以及没有考虑 recursion depth。
我通常会在写代码前先定义： base case、visited logic 和 traversal scope。
2️⃣3️⃣ 什么时候 DFS 适用？
Good Fit
当题目问：
path existence
connected components
explore all possibilities
tree recursion
grid region traversal
cycle detection
backtracking
topological exploration
subtree information
Problem Signals
看到这些关键词想到 DFS：
all paths
exists path
connected
island
component
cycle
recursive
subtree
valid tree
backtracking
permutations
combinations
👉 面试回答
当题目需要 deep exploration、 connected component detection、 path existence、 cycle detection、 tree recursion， 或 backtracking 时， 我会考虑 DFS。
如果问题可以自然地用 recursion 表达， DFS 通常很合适。
2️⃣4️⃣ 什么时候 DFS 不适用？
Not Good Fit
DFS 可能不适合：
need shortest path in unweighted graph
need minimum number of moves
need level-order traversal
need nearest target
large recursion depth risk
Better Alternatives
| Problem Type | Better Pattern |
|---|---|
| Shortest path unweighted | BFS |
| Weighted shortest path | Dijkstra |
| Level-order traversal | BFS |
| Nearest source distance | Multi-source BFS |
| Very deep recursion | Iterative DFS / BFS |
| Optimization with overlapping subproblems | Dynamic Programming |
👉 面试回答
DFS 不是所有 traversal 问题的最佳选择。
如果题目问 unweighted graph 中的 shortest path 或 minimum steps， BFS 通常更好， 因为 BFS 是按 level 扩展。
如果 recursion depth 很深， iterative DFS 或 BFS 可能更安全。
2️⃣5️⃣ 标准模板
Tree DFS Template
def dfs(root):
if not root:
return
# process root
dfs(root.left)
dfs(root.right)
Tree DFS With Return Value
def dfs(root):
if not root:
return base_value
left = dfs(root.left)
right = dfs(root.right)
return combine(root, left, right)
Graph DFS Template
def dfs(node):
if node in visited:
return
visited.add(node)
for neighbor in graph[node]:
dfs(neighbor)
Grid DFS Template
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if grid[r][c] != target_value:
return
grid[r][c] = visited_value
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
Iterative DFS Template
def dfs_iterative(start):
stack = [start]
visited = set([start])
while stack:
node = stack.pop()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)
Directed Graph Cycle Detection Template
def has_cycle(graph, n):
state = [0] * n
def dfs(node):
if state[node] == 1:
return True
if state[node] == 2:
return False
state[node] = 1
for neighbor in graph[node]:
if dfs(neighbor):
return True
state[node] = 2
return False
for node in range(n):
if state[node] == 0:
if dfs(node):
return True
return False
🧠 Staff-Level Answer Final
👉 面试回答完整版本
DFS，也就是 Depth-First Search， 是一种先沿着一个 branch 尽可能深入探索， 然后再 backtrack 的 traversal algorithm。
DFS 可以用 recursion 实现， 也可以用 explicit stack 迭代实现。
DFS 特别适合 tree traversal、graph traversal、connected components、path existence、cycle detection、grid region traversal 和 backtracking。
在 tree problems 中， DFS 和 recursion 非常自然地对应。 对每个 node， 我们处理当前 node， 然后递归处理 left 和 right children。 根据 root 处理的位置不同， 可以得到 preorder、inorder 或 postorder traversal。
DFS 也可以从 child 向 parent 返回信息。 比如 maximum depth 返回 1 + 左右子树最大深度。 Balanced tree checking 可以返回 subtree height， 并向上传播 failure。
在 graph problems 中， DFS 必须考虑 visited set， 因为 graph 可能有 cycles。 我通常在探索 neighbors 之前 mark visited， 防止 infinite recursion 和 duplicate work。
对 disconnected graph， 我会遍历所有 nodes， 并从每个 unvisited node 启动 DFS。 每次新的 DFS 会访问一个完整 connected component。
在 grid problems 中， 每个 cell 可以看成 graph node。 Base cases 包括 boundary check、obstacle check 和 visited check。 Number of Islands 和 Flood Fill 是经典例子。
DFS 也常用于 cycle detection。 在 undirected graph 中， 我会携带 parent。 如果访问到一个 visited neighbor， 且它不是 parent， 说明存在 cycle。
在 directed graph 中， 我会用三种状态： unvisited、visiting 和 visited。 如果 DFS 访问到 visiting node， 说明存在 back edge，也就是 cycle。
Backtracking 是 decision tree 上的 DFS。 它遵循 choose、explore、unchoose。 常用于 permutations、combinations、subsets 和其他 search problems。
DFS 的复杂度通常是： tree 是 O(n)， graph 是 O(V + E)， grid 是 O(mn)。 Space complexity 取决于 recursion depth 或 explicit stack size。
高级工程师解释 DFS 时， 我会讲清楚： node 或 state 是什么， base case 是什么， neighbor 怎么生成， visited 如何维护， 是否需要处理 disconnected components， 以及 DFS 是只做 traversal， 还是需要把信息 return upward。
⭐ Final Insight
DFS 的核心不是“写递归”。
它的核心是 deep exploration + backtracking。
Senior-level 的重点是：
node/state 是什么， base case 是什么， visited 什么时候标记， neighbor 如何生成， 是否需要处理 disconnected components， 以及 DFS 是 traversal，还是需要 return information upward。
能讲清楚这些， DFS 就是一种处理 tree、graph、grid、cycle detection 和 backtracking 的通用搜索模型。
Implement