Complexity Analysis
Visits every vertex once and examines every edge once. Space comes from the recursion stack (up to V deep) plus the visited set storing V nodes.
Recognize This Pattern When...
Pattern Signals
- Need to explore all paths or find any valid path
- Graph traversal where order of exploration does not matter
- Detecting cycles in a graph
- Tree traversal (preorder, inorder, postorder)
- Backtracking problems (permutations, combinations, subsets)
- Connected components in undirected graphs
- Finding if a path exists between two nodes
Preconditions
- Graph or tree structure (adjacency list, matrix, or node references)
- Need to track visited nodes to avoid infinite loops in cyclic graphs
- Problem can be solved by exploring paths one at a time
When NOT to Use
- Finding the shortest path in an unweighted graph (use BFS).
- Very deep graphs where recursion may cause stack overflow (use iterative DFS or BFS).
- Level-order traversal or minimum steps by distance is required (use BFS).
- Need to find nodes at a specific distance from source (use BFS).
Why It Works
DFS commits fully to one path before trying alternatives. When you hit a dead end (a node with no unvisited neighbors), you backtrack to the most recent node that still has unexplored paths. This "go deep then backtrack" behavior comes from recursion or an explicit stack. Important distinction: DFS traversal visits each node once (mark visited, never revisit) with O(V+E) time. Backtracking search (permutations, N-Queens) explores all possible paths by undoing choices, which can be exponential. Both use the same stack-based exploration pattern, but backtracking deliberately revisits states to enumerate solutions.
The Analogy
Picture yourself exploring a maze. You pick one direction and keep walking until you hit a wall. Then you backtrack to the last intersection and try a different path. You keep doing this until you have explored every corridor. DFS works the same way: commit to a path, hit a dead end, backtrack, repeat.
The Canonical Problem
Number of Islands
mediumGiven a 2D grid of "1"s (land) and "0"s (water), count the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically.
Solve on LeetCodeAlgorithm Template
Generic template you can adapt to most dfs (depth-first search) problems.
def dfs_traversal(graph, start):
visited = set()
def dfs(node):
if node in visited:
return
visited.add(node)
# Process node here
for neighbor in graph[node]:
dfs(neighbor)
dfs(start)
return visitedImplementations
Complete examples with explanations. Copy-paste and adapt to your problem.
def count_islands(grid: list[list[str]]) -> int:
"""
Count connected components of '1's in a 2D grid.
Uses DFS with nested helper to mark visited cells.
Time: O(rows * cols), Space: O(rows * cols) for visited set
"""
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
visited = set()
islands = 0
def dfs(r, c):
# Base cases: out of bounds, water, or already visited
if (r < 0 or r >= rows or c < 0 or c >= cols
or grid[r][c] == '0' or (r, c) in visited):
return
visited.add((r, c))
# Explore all 4 directions
dfs(r + 1, c) # down
dfs(r - 1, c) # up
dfs(r, c + 1) # right
dfs(r, c - 1) # left
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1' and (r, c) not in visited:
dfs(r, c)
islands += 1
return islands
# Example usage
grid = [
['1', '1', '0', '0', '0'],
['1', '1', '0', '0', '0'],
['0', '0', '1', '0', '0'],
['0', '0', '0', '1', '1']
]
print(count_islands(grid)) # 3
# Variant: Path Sum (Binary Tree)
def has_path_sum(root, target_sum):
"""Check if tree has root-to-leaf path summing to target."""
def dfs(node, remaining):
if not node:
return False
remaining -= node.val
# Leaf node check
if not node.left and not node.right:
return remaining == 0
return dfs(node.left, remaining) or dfs(node.right, remaining)
return dfs(root, target_sum)The nested helper pattern keeps visited state in closure scope, so you don't pass it as a parameter. The outer function handles setup and iteration over potential starting points.
/**
* Count connected components of '1's in a 2D grid.
* Uses DFS with nested helper to mark visited cells.
*
* Time: O(rows * cols), Space: O(rows * cols) for visited set
*/
function countIslands(grid) {
if (!grid || !grid.length || !grid[0].length) {
return 0;
}
const rows = grid.length;
const cols = grid[0].length;
const visited = new Set();
let islands = 0;
function dfs(r, c) {
const key = `${r},${c}`;
// Base cases: out of bounds, water, or already visited
if (r < 0 || r >= rows || c < 0 || c >= cols
|| grid[r][c] === '0' || visited.has(key)) {
return;
}
visited.add(key);
// Explore all 4 directions
dfs(r + 1, c); // down
dfs(r - 1, c); // up
dfs(r, c + 1); // right
dfs(r, c - 1); // left
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
const key = `${r},${c}`;
if (grid[r][c] === '1' && !visited.has(key)) {
dfs(r, c);
islands++;
}
}
}
return islands;
}
// Example usage
const grid = [
['1', '1', '0', '0', '0'],
['1', '1', '0', '0', '0'],
['0', '0', '1', '0', '0'],
['0', '0', '0', '1', '1']
];
console.log(countIslands(grid)); // 3
// Iterative DFS using explicit stack
function countIslandsIterative(grid) {
if (!grid || !grid.length) return 0;
const rows = grid.length;
const cols = grid[0].length;
const visited = new Set();
let islands = 0;
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
const startKey = `${r},${c}`;
if (grid[r][c] === '1' && !visited.has(startKey)) {
// Start new island - use stack instead of recursion
const stack = [[r, c]];
while (stack.length > 0) {
const [cr, cc] = stack.pop();
const key = `${cr},${cc}`;
if (visited.has(key)) continue;
if (cr < 0 || cr >= rows || cc < 0 || cc >= cols) continue;
if (grid[cr][cc] === '0') continue;
visited.add(key);
for (const [dr, dc] of directions) {
stack.push([cr + dr, cc + dc]);
}
}
islands++;
}
}
}
return islands;
}JavaScript implementation showing both recursive and iterative approaches. The iterative version uses an explicit stack, which avoids stack overflow for very deep traversals.
Pattern Variations
Preorder / Inorder / Postorder Traversal
O(n) / O(h)Tree traversal variants that differ in when you process the current node relative to its children. Preorder processes before children, inorder processes between left and right, postorder processes after both children.
Cycle Detection
O(V + E) / O(V)Detect cycles in directed graphs using DFS with three states: unvisited, visiting (in current path), and visited (fully explored). A back edge to a "visiting" node indicates a cycle.
Topological Sort
O(V + E) / O(V)Order vertices so that for every directed edge u->v, u comes before v. Run DFS and add nodes to result in postorder (after all descendants are processed).
Connected Components
O(V + E) / O(V)Find all groups of connected nodes in an undirected graph. Run DFS from each unvisited node, marking all reachable nodes as part of the same component.
Iterative DFS with Stack
O(V + E) / O(V)Replace recursion with an explicit stack to avoid stack overflow on deep graphs. Push neighbors onto the stack and pop to get the next node to visit.
Practice Problems
| Problem | Difficulty | Type | Notes |
|---|---|---|---|
| Number of Islands | medium | canonical | Classic grid DFS - count connected components of land cells |
| Path Sum | easy | canonical | Binary tree DFS checking if any root-to-leaf path sums to target |
| Clone Graph | medium | variant | DFS to traverse and clone each node, using a hash map to track cloned nodes |
| Course Schedule | medium | variant | Cycle detection in directed graph using DFS with three-color marking |
| Course Schedule II | medium | follow-up | Topological sort - return valid course order or empty if cycle exists |
| Max Area of Island | medium | variant | Similar to Number of Islands but track size of each component |
| Surrounded Regions | medium | variant | DFS from border cells to find which regions should not be flipped |
| Word Search | medium | variant | DFS with backtracking to find if word exists in grid |
| Binary Tree Maximum Path Sum | hard | follow-up | DFS tracking max path sum through each subtree |
| All Paths From Source to Target | medium | variant | DFS with backtracking to enumerate all paths in a DAG |
Interview Tips
- Before coding, clarify whether the graph is directed or undirected - this affects cycle detection and visited tracking
- Always ask about graph size and depth to decide between recursive and iterative DFS
- For grid problems, explicitly mention the four directions (up, down, left, right) and handle bounds checking clearly
- Explain why you chose DFS over BFS: "I need to explore full paths" or "order does not matter and DFS is simpler"
- When detecting cycles, explain the three-state approach (white/gray/black or unvisited/visiting/visited)
- Mention that recursive DFS can hit stack limits - offer the iterative version if the interviewer seems concerned
- Know the DFS state patterns: (1) visited set for undirected graphs/reachability, (2) 3-color (0/1/2) for directed cycle detection, (3) parent pointer for undirected cycle detection, (4) enter/exit times for ancestor queries and topological ordering, (5) backtracking state (choose-recurse-undo) for enumeration problems
- For deep graphs: Python default recursion limit is 1000 (can increase with sys.setrecursionlimit but risky). JS has no fixed limit but can still crash. Grid DFS worst case is O(rows * cols) depth. Switch to iterative when depth could exceed a few thousand.
Common Follow-up Questions
What is the difference between DFS and BFS?
CommonDFS goes deep before wide, using a stack (implicit via recursion or explicit). BFS goes wide before deep, using a queue. DFS is better for path finding, cycle detection, and topological sort. BFS is better for shortest path in unweighted graphs and level-order traversal. Both have O(V + E) time complexity.
How do you convert recursive DFS to iterative?
CommonReplace the call stack with an explicit stack data structure. Push the starting node, then in a loop: pop a node, skip if visited, mark as visited, process it, and push all unvisited neighbors. The main difference is that the explicit stack processes neighbors in reverse order compared to recursion.
How do you prevent stack overflow in deep graphs?
CommonUse iterative DFS with an explicit stack instead of recursion. Python has a default recursion limit of 1000 (can increase with sys.setrecursionlimit() but this is risky as it can cause segfaults). JavaScript has no fixed limit but can still crash. For grid DFS, worst case depth is O(rows * cols). As a rule of thumb, switch to iterative DFS when depth could exceed a few thousand nodes. The iterative approach uses heap memory for the stack, which is typically much larger than the call stack.
How do you handle disconnected graphs?
CommonRun DFS from every unvisited node, not just one starting point. Loop through all nodes and call DFS on any that have not been visited. This ensures you explore every connected component.
How do you detect a cycle in a directed vs undirected graph?
CommonFor undirected graphs, a cycle exists if you visit a node that is already visited and is not the parent of the current node. For directed graphs, use three states: unvisited, visiting (in current DFS path), and visited (fully explored). A cycle exists if you reach a "visiting" node from another "visiting" node.
What are the common DFS state patterns?
CommonFive key patterns: (1) Simple visited set - for undirected graphs and reachability; (2) 3-color marking (unvisited/visiting/visited or 0/1/2) - for directed cycle detection, where finding a "visiting" node means cycle; (3) Parent pointer - for undirected cycle detection, ignore the edge back to parent; (4) Enter/exit timestamps - for ancestor queries, topological ordering, and finding back edges; (5) Backtracking state (choose, recurse, undo) - for enumeration problems like permutations and N-Queens where you need to explore all possibilities.
Common Mistakes
Forgetting to mark nodes as visited before recursing
# WRONG: Mark after recursive calls
def dfs(node):
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
visited.add(node) # Too late - may revisit nodeFix: Mark the node as visited immediately when you first encounter it, before processing neighbors. This prevents the same node from being added to the stack multiple times in graphs with cycles or multiple paths to the same node.
Not handling disconnected components
# WRONG: Only DFS from node 0
def count_components(graph):
visited = set()
dfs(0, graph, visited)
return 1 # Misses disconnected partsFix: Loop through all nodes and run DFS from each unvisited node. Count how many times you start a new DFS to get the number of connected components.
Infinite recursion from missing base case
# WRONG: No check for visited nodes
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
dfs(neighbor) # Will revisit already-visited nodesFix: Always check if a node has been visited before recursing. Either skip visited nodes with an if statement, or return early at the start of the function if the node is already in the visited set.
Using DFS when BFS is required
# WRONG: DFS for shortest path
def shortest_path(graph, start, end):
visited = set()
def dfs(node, depth):
if node == end:
return depth
# ... DFS logic
return dfs(start, 0) # May not find shortest pathFix: DFS does not guarantee shortest path because it may find a longer path first. For unweighted shortest path problems, always use BFS. DFS is appropriate when any path works or when you need to explore all paths.
Frequently Asked Questions
When should I use DFS instead of BFS?
Use DFS when you need to explore all paths, detect cycles, perform topological sort, or when the solution is likely deep in the graph. DFS also has simpler code for tree problems due to natural recursion. Use BFS when you need the shortest path in an unweighted graph or need to process nodes by distance from the source.
What is the time and space complexity of DFS?
Time complexity is O(V + E) where V is vertices and E is edges, because each vertex and edge is visited once. Space complexity is O(V) for the visited set plus O(V) for the recursion stack in the worst case (a linear graph), giving O(V) total.
How do I implement DFS iteratively?
Replace recursion with an explicit stack. Initialize the stack with the starting node. While the stack is not empty: pop a node, skip if already visited, mark it as visited, process it, and push all unvisited neighbors onto the stack. This mirrors the call stack behavior of recursive DFS.
Why use a nested helper function for DFS?
The nested helper pattern lets you share state (like the visited set) through closure instead of passing it as a parameter. This makes the code cleaner and matches how most people reason about the algorithm. The outer function sets things up; the inner function does the actual traversal.
How does DFS relate to backtracking?
Backtracking is DFS with pruning and undoing choices. In standard DFS you mark visited and never unmark. In backtracking you mark a choice, recurse, then unmark (backtrack) to try other choices. Problems like permutations, combinations, and N-Queens use backtracking, which is a specialized form of DFS.
Can DFS handle weighted graphs?
DFS can traverse weighted graphs, but it will not find the shortest path by edge count or weight. For shortest path in weighted graphs, use Dijkstra (non-negative weights) or Bellman-Ford (handles negative weights). DFS is still useful for connectivity checks and path existence in weighted graphs.