DFS - Coding Interview Prep

What is DFS?

DFS (depth-first search) explores as far as possible along one path before backtracking. It uses the call stack (recursive) or an explicit stack (iterative) to track the current path. The defining behavior: commit to one direction, go to the end, and only then try another direction.

DFS is the natural traversal for trees. Every binary tree recursive function that calls itself on left and right subtrees is performing DFS - you go all the way to a leaf, compute a result, and propagate it back up. The vast majority of tree interview problems are DFS problems in disguise.

The key distinction from BFS: DFS does not guarantee shortest path (it might find a very long path first), but it naturally enumerates all paths and can prune early when a path violates a constraint. That pruning capability is what makes backtracking tractable.

Backtracking is DFS with undo: you make a choice, recurse into it, then undo that choice before trying the next option. This explores the entire decision tree while using only O(depth) space - you reuse the same path list for every branch by appending before recursing and popping on return.

Core operations

Variant	Implementation	State tracking	Typical use
Recursive DFS	Call stack	`visited` set or mutation	Tree traversal, connected components
Iterative DFS	Explicit stack	`visited` set	Same as recursive; avoids stack overflow
Backtracking	Recursive + undo	Mutable `path` list	Permutations, combinations, constraint satisfaction
Memoized DFS	Recursive + cache	`memo` dict	Overlapping subproblems (see Dynamic Programming)

Key patterns

Standard DFS (connected components / reachability)

Mark a node visited before recursing into its neighbors. Each DFS call from an unvisited node discovers one connected component - it will visit every node reachable from the start and nothing more.

When to use - you need to know whether one node reaches another, or you need to count or label the connected components of a graph or grid (islands, regions, friend circles). One pass touches every node and edge once at O(V + E), where re-exploring nodes from scratch would blow up.

How it works - recurse from the start node, and the very first thing each call does is mark the current node visited so it is never entered twice. Then recurse into each unvisited neighbor. The marking is what handles cycles: a graph can loop back on itself, and without the visited check the recursion would never stop. On a grid you can skip the separate visited set and mark in place instead, flipping the cell value so the base case rejects it on the next visit. A recursive call uses the call stack; an explicit stack does the same job iteratively and avoids stack overflow on deep graphs.

VisualizationDepth-first search

0/18

start

visited

call stack

visit order

Descend into 0: push it and mark visited.

def dfs(adj, node, visited, order):▶    visited.add(node)▶    order.append(node)    for nbr in sorted(adj[node]):        if nbr not in visited:            dfs(adj, nbr, visited, order)    return order

Note

Mark visited before recursing, not after - if you mark on return, a node reachable from two different paths gets visited twice and causes infinite recursion in cyclic graphs. Mark immediately upon first discovery.

Backtracking

Maintain a mutable path list. At each step, add a candidate to the path, recurse, then remove it (undo). This explores all possibilities without allocating a new list for every branch. The base case records a result when the path satisfies the completion condition.

When to use - the problem asks you to enumerate all valid arrangements: every combination, permutation, subset, or root-to-leaf path. The phrase "generate all" or "find all" is the signal. The decision tree of choices is exponential, but backtracking walks it directly and prunes dead branches early instead of building every candidate from scratch.

How it works - at each level you make one choice, append it to the shared path, and recurse one level deeper. When the path is complete you record a snapshot of it, then on the way back up you pop that choice off so the next branch starts clean. The same path list is reused for every branch, which is why the space cost is only O(depth) instead of one list per candidate. Two things matter: record path[:] (a copy), since the live path keeps mutating after you store it, and undo every choice on return so branches do not contaminate each other. Adding a guard before recursing - a partial path that already violates the constraint - prunes whole subtrees and is what keeps the search tractable.

VisualizationBacktracking

0/27

target

paths found

call stack

dfs(5)

current path

Choose 5. Need 17 more from here down.

def path_sum(node, target, path, results):    if not node:        return▶    path.append(node.val)            # choose▶    remaining = target - node.val    if not node.left and not node.right and remaining == 0:        results.append(path[:])      # record a snapshot of the path    path_sum(node.left, remaining, path, results)    path_sum(node.right, remaining, path, results)    path.pop()                       # undo (backtrack)

Note

Append path[:] not path - path is a mutable list that will be modified by future recursive calls. Recording path directly stores a reference that changes; path[:] captures the current snapshot.

Canonical examples

Number of islands

A grid where '1' cells represent land and '0' represents water. DFS from any unvisited '1' cell marks all connected land cells by sinking them (setting to '0'). Each DFS launch from an unvisited '1' discovers one island. No explicit visited set needed - mutation of the grid serves as the visited marker.

Try it

Python

Loading editor…

Tests

assert num_islands([['1','1','1','1','0'],['1','1','0','1','0'],['1','1','0','0','0'],['0','0','0','0','0']]) == 1

assert num_islands([['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']]) == 3

assert num_islands([['0','0','0'],['0','0','0']]) == 0

assert num_islands([['1']]) == 1

assert num_islands([['1','0','1'],['0','0','0'],['1','0','1']]) == 4

Hints (3)

Generate all permutations (backtracking)

Build every valid permutation by choosing one unused element at each position, recursing, then un-choosing it. A used boolean array tracks availability in O(1) per check - this avoids constructing a new "remaining elements" list on every recursive call.

Try it

Python

Loading editor…

Tests

assert sorted(permutations([1, 2, 3])) == [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

assert permutations([1]) == [[1]]

assert sorted(permutations([1, 2])) == [[1, 2], [2, 1]]

assert len(permutations([1, 2, 3, 4])) == 24

assert permutations([]) == [[]]

Hints (3)

Note

Backtracking prunes the search space - add pruning conditions before recursing - if the current partial path can never lead to a valid solution (sum exceeds target, required element already used), return early. Without pruning, backtracking can be exponential; with it, many problems become tractable.

When to reach for DFS

The problem involves traversing or searching a tree - virtually all tree problems use DFS.
You need to find or count connected regions in a grid (islands, flood fill, regions).
The problem asks you to generate all combinations, permutations, or subsets - backtracking DFS.
You need to detect a cycle in a directed or undirected graph.
The problem involves path finding where you need to explore all paths (not just the shortest).
You're exploring a decision tree where each node represents a choice and you need all valid leaves.

Practice problems

Number of Islands - Grid DFS; mutation as visited marker.
Max Area of Island - Same grid DFS, return accumulated area instead of count.
Path Sum - Tree DFS; carry a running sum down the path.
Word Search - Grid backtracking; mark visited with mutation, undo on return.
Subsets - Backtracking; no pruning needed, just include/exclude each element.
Letter Combinations of a Phone Number - Backtracking over character choices per digit.