53 questions using this pattern
Explore as deep as possible along each branch before backtracking, using recursion or an explicit stack. DFS is memory-efficient and naturally suited for problems involving paths, connectivity, and exhaustive exploration.
Imagine exploring a maze by always taking the first available turn until you hit a dead end. Then you backtrack to the last intersection and try the next option. You keep going deeper until stuck, then retreat and try alternatives.
Another analogy: reading a "choose your own adventure" book. You follow one story path all the way to its ending, then go back and explore different choices you didn't take.
DFS uses a stack (LIFO)—either the call stack via recursion or an explicit stack data structure. This naturally explores depth-first: the most recently discovered node is explored first.
The key insight is that DFS maintains the current path from root to current node on the stack. This makes it perfect for:
Unlike BFS, DFS doesn't guarantee shortest paths, but it uses O(h) memory (height of tree/recursion depth) vs BFS's O(w) (width of level).
def dfs(root): if not root: return [] result = [] stack = [root] while stack: # Pop top node node = stack.pop() result.append(node.val) # Push right first, then left (so left is popped first) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return resultWe have a binary tree. Our goal is to visit all nodes depth-first: go as deep as possible down each branch before backtracking.
Example: DFS traversal of graph
Graph:
A --- B --- E
| |
C --- D --- F
DFS from A (alphabetical order):
Visit A → explore neighbors
Visit B → explore neighbors
Visit D → explore neighbors
Visit C (already visited? skip or detect cycle)
Visit F → no unvisited neighbors, backtrack
Backtrack to D, backtrack to B
Visit E → no unvisited neighbors, backtrack
Backtrack to B, backtrack to A
Visit C → D already visited, backtrack
Done
Order visited: A → B → D → F → E → C
Recursion call stack visualization:
dfs(A)
└─ dfs(B)
└─ dfs(D)
└─ dfs(F) ← returns
└─ dfs(C) ← already visited
└─ dfs(E) ← returns
└─ dfs(C) ← already visited
Cycle detection with colors:
WHITE (0) = unvisited
GRAY (1) = in current path (on stack)
BLACK (2) = fully processed
If we visit a GRAY node → cycle detected!
Use this skeleton as a starting point for problems using this pattern:
def dfs_recursive(graph: dict, start: str, visited: set = None) -> list:
"""Basic recursive DFS traversal."""
if visited is None:
visited = set()
visited.add(start)
result = [start]
for neighbor in graph[start]:
if neighbor not in visited:
result.extend(dfs_recursive(graph, neighbor, visited))
return result
def dfs_iterative(graph: dict, start: str) -> list:
"""Iterative DFS using explicit stack."""
visited = set()
stack = [start]
result = []
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
result.append(node)
# Add neighbors in reverse for same order as recursive
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
return result
def dfs_path_finding(graph: dict, start: str, end: str) -> list:
"""Find a path from start to end using DFS."""
def dfs(node: str, path: list) -> list:
if node == end:
return path
for neighbor in graph[node]:
if neighbor not in path: # Avoid cycles
result = dfs(neighbor, path + [neighbor])
if result:
return result
return []
return dfs(start, [start])
def detect_cycle(graph: dict) -> bool:
"""Detect cycle in directed graph using DFS."""
WHITE, GRAY, BLACK = 0, 1, 2
color = {node: WHITE for node in graph}
def dfs(node: str) -> bool:
color[node] = GRAY # Mark as being processed
for neighbor in graph[node]:
if color[neighbor] == GRAY: # Back edge = cycle
return True
if color[neighbor] == WHITE and dfs(neighbor):
return True
color[node] = BLACK # Mark as complete
return False
return any(color[node] == WHITE and dfs(node) for node in graph)
def topological_sort(graph: dict) -> list:
"""Topological sort using DFS (Kahn's algorithm alternative)."""
visited = set()
result = []
def dfs(node: str):
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs(neighbor)
result.append(node) # Add after all descendants
for node in graph:
if node not in visited:
dfs(node)
return result[::-1] # Reverse for topological orderLook for these keywords and patterns in problem descriptions:
Recursive DFS on large graphs or trees can exceed Python's default recursion limit (usually 1000), causing a stack overflow.
Fix:
Either increase the limit with sys.setrecursionlimit(10000) or convert
to iterative DFS with an explicit stack. Iterative is safer for unknown
input sizes.
In iterative DFS, checking visited only when popping (not when pushing) allows the same node to be added multiple times, wasting memory.
Fix:
For iterative DFS, either check when popping (simpler but less efficient) or mark visited when pushing (more efficient):
if neighbor not in visited:
visited.add(neighbor) # Mark when adding
stack.append(neighbor)
Visit nodes in specific orders relative to processing children. Preorder visits parent first, inorder visits between children, postorder visits parent last.
Examples: Binary Tree Inorder Traversal, Serialize/Deserialize BST
Traverse all reachable nodes from a starting point. Need to track visited nodes to avoid infinite loops in cyclic graphs.
Examples: Number of Islands, Clone Graph, Course Schedule
Explore paths and undo choices when they don't lead to a solution. The natural call stack provides the backtracking mechanism.
Examples: N-Queens, Sudoku Solver, Permutations
Cache results of DFS from each node to avoid recomputation. Transforms DFS into dynamic programming for certain problems.
Examples: Longest Increasing Path in Matrix, Word Break
Run DFS with increasing depth limits. Combines BFS's shortest-path guarantee with DFS's memory efficiency.
Examples: Finding shortest path when memory is limited
Start here to build foundational understanding.
Master the pattern with these representative problems.
Test your mastery with complex variations.
Explore similar techniques:
Level-by-level traversal using a queue, exploring all neighbors at the current depth before moving deeper. This guarantees the shortest path in unweighted graphs and is ideal for problems requiring layer-by-layer processing.
Navigate 2D grids systematically using DFS, BFS, or directional iteration. Matrix traversal combines graph traversal concepts with coordinate-based movement, treating each cell as a node connected to its neighbors.
Build solutions incrementally, exploring choices one at a time and abandoning paths that fail to satisfy constraints. Backtracking systematically explores all possibilities by making a choice, recursing, then undoing the choice.
Visit all nodes in a binary tree in specific orders: preorder (root-left-right), inorder (left-root-right), postorder (left-right-root), or level-order (BFS). Each order reveals different structural information about the tree.
For cycle detection in directed graphs, using a simple visited set doesn't distinguish between "node in current path" (cycle) and "node fully processed" (not a cycle, just already explored).
Fix:
Use three states (WHITE/GRAY/BLACK) or track the current path separately. A cycle exists only if you revisit a node that's still on the current path.
Adding nodes to result before processing descendants gives reverse topological order or incorrect order entirely.
Fix:
Add nodes to result only after all descendants are processed (post-order). Then reverse the result at the end.