13 DFS Problems for Coding Interviews, Ordered From Easy to Hard

Studying DFS patterns vs actually getting DFS in an interview

Depth-first search shows up in roughly 25% of all coding interview rounds. Not because companies love tree recursion for its own sake, but because DFS is the substrate for cycle detection, path finding, backtracking, connected components, and a handful of classical graph algorithms. Learn the shape once and you start recognizing it everywhere.

Except there are 13 distinct shapes. And the hard ones look nothing like the easy ones when you are sitting in a Zoom call at 11 AM with a blank editor.

These 13 DFS problems are ordered by what they actually teach. Each introduces a new variant. Later problems build on earlier ones. Work through them in sequence and the hard ones stop looking alien.

If you want to understand which variant fits which signal before any of these, start with the DFS pattern recognition guide. If you need the algorithm mechanics first, read depth-first search from scratch.

1. Maximum Depth of Binary Tree (LC 104, Easy)

The simplest DFS problem there is. Also the one that teaches you everything.

def maxDepth(root):
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

This is the base template for postorder DFS. Base case on null. Recurse into children. Combine results on the way back up. Every DFS problem that computes a value from subtrees uses some version of this shape.

The mistake beginners make: checking if not root.left and not root.right instead of if not root. You test null at entry, not at the leaf. Five characters. Get them right every time or you will spend 10 minutes debugging a leaf count that is off by one.

2. Number of Islands (LC 200, Medium)

The canonical grid DFS. Find each unvisited "1", flood-fill it to "0", increment the count.

def numIslands(grid):
    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == '1':
                dfs(grid, r, c)
                count += 1
    return count

The outer loop is not cosmetic. You call DFS once per connected component, not once per cell. Miss this and your single-island input accidentally counts every cell. Disconnected graphs require this pattern. This exact structure reappears in Course Schedule, Longest Increasing Path, and almost every graph traversal problem you will encounter.

3. Path Sum (LC 112, Easy)

Here DFS passes state down the call stack instead of aggregating upward. Same traversal direction, opposite information flow.

def hasPathSum(root, targetSum):
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == targetSum
    return (hasPathSum(root.left, targetSum - root.val) or
            hasPathSum(root.right, targetSum - root.val))

The leaf check is not root.left and not root.right. An empty child is not a leaf. Get this wrong and you count null children as valid path endpoints, which gives you wrong answers on any tree where a node has exactly one child. The interview does not go great after that.

4. Clone Graph (LC 133, Medium)

DFS on a general graph instead of a tree. The new piece is a hash map.

def cloneGraph(node, visited={}):
    if not node:
        return None
    if node in visited:
        return visited[node]
    clone = Node(node.val)
    visited[node] = clone
    for neighbor in node.neighbors:
        clone.neighbors.append(cloneGraph(neighbor, visited))
    return clone

The hash map does double duty. It is both the visited set (prevents infinite loops in cycles) and the result cache (returns the already-cloned node when you hit it a second time). Without it, a cyclic graph sends you into infinite recursion. Not a hypothetical. That is literally what happens. Every DFS on a non-tree graph needs this pattern.

5. Surrounded Regions (LC 130, Medium)

Do not try to find enclosed Os directly. Find the ones that are not enclosed, then flip everything else.

Border-connected Os are safe. DFS from every O on the grid edge, marking safe cells. Everything unmarked gets captured.

This is the inverse thinking pattern. When the target set is hard to identify directly, define its complement and subtract. The insight feels obvious in hindsight and invisible before you see it. You will see this exact reversal in Pacific Atlantic Water Flow and several other grid problems.

6. Course Schedule (LC 207, Medium)

Cycle detection on a directed graph. A boolean visited set gives false positives on directed graphs. You need three states.

# 0 = unvisited, 1 = on current stack, 2 = fully processed
def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    for a, b in prerequisites:
        graph[b].append(a)
    state = [0] * numCourses

    def dfs(v):
        if state[v] == 1: return False  # back edge = cycle
        if state[v] == 2: return True
        state[v] = 1
        for neighbor in graph[v]:
            if not dfs(neighbor):
                return False
        state[v] = 2
        return True

    return all(dfs(v) for v in range(numCourses))

State 1 means "on the current recursion stack." A gray-to-gray edge is a back edge, which proves a cycle. A boolean visited array cannot distinguish "in my current path" from "verified clean in a previous path." Think of it as a traffic light: unvisited, active, done. This 3-color scheme applies to any directed cycle detection problem.

7. Word Search (LC 79, Medium)

DFS with an undo step. This is what backtracking actually is.

def dfs(r, c, idx):
    if idx == len(word):
        return True
    if r < 0 or r >= R or c < 0 or c >= C or board[r][c] != word[idx]:
        return False
    board[r][c] = '#'          # mark visited
    found = any(dfs(r+dr, c+dc, idx+1) for dr, dc in dirs)
    board[r][c] = word[idx]    # restore
    return found

The mark-restore pair is the entire difference between DFS and backtracking. You mutate state to explore, then undo so the next path sees clean state. Omit the restore step and paths that come after will see consumed cells and fail. The bug only appears when a cell is needed twice across different paths, meaning most of your test cases pass fine. The interviewer's edge case does not.

When you forget the restore step, everything looks fine until it doesn't

"Forgot to restore board[r][c]? Your test cases pass. The interviewer's test cases do not."

The deeper mechanics of what backtracking actually means are in the backtracking guide.

8. Binary Tree Maximum Path Sum (LC 124, Hard)

The function returns the maximum single-arm gain to its parent. But it also updates a global max using both arms simultaneously. Two different things happen in one call.

def maxPathSum(root):
    max_sum = [float('-inf')]

    def dfs(node):
        if not node:
            return 0
        left = max(0, dfs(node.left))
        right = max(0, dfs(node.right))
        max_sum[0] = max(max_sum[0], node.val + left + right)
        return node.val + max(left, right)

    dfs(root)
    return max_sum[0]

max(0, gain) discards subtrees that hurt the sum. You cannot return a fork path to the parent because a path cannot branch, so you return the single arm while recording the fork result locally. This is confusing every time you read it. That is not a sign you do not understand it. The dual-return pattern is genuinely subtle. It appears in diameter of binary tree, binary tree cameras, and a handful of other hard tree problems.

9. Pacific Atlantic Water Flow (LC 417, Medium)

Running DFS forward (from each cell outward to both oceans) requires O(mn) separate DFS calls. Running it backward (which cells can each ocean reach going uphill?) runs in O(mn) total.

Multi-source DFS from all Pacific border cells going uphill. Then the same from Atlantic borders. Intersect the two result sets.

This is the reverse multi-source DFS pattern. When the forward direction forces you to restart DFS for every candidate, flip the direction and run once from the destination set. You already saw this inverse logic in Surrounded Regions. At this point you should be naming the pattern before reading the full constraints. That recognition is the skill this list is building.

10. Serialize and Deserialize Binary Tree (LC 297, Hard)

Preorder DFS emits each node in the order it is visited, with null markers for absent children. The resulting string uniquely encodes tree shape.

Tree:        Serialized: "1,2,null,null,3,4,null,null,5,null,null"
    1
   / \
  2   3
     / \
    4   5

Deserialization reads this sequence left-to-right, recursively building the tree. Use a deque and popleft() for O(n) reconstruction. Passing an index by value forces you to return it alongside the node at every recursive call, which makes the code significantly harder to follow.

Preorder uniquely determines a tree if you record nulls. Inorder alone does not. The structural encoding insight here is the same one behind XML and most recursive data formats. File it under "things that seem complicated until you realize they are just preorder DFS."

11. Longest Increasing Path in Matrix (LC 329, Hard)

DFS from each cell, cache results. No cycle is possible because the strictly-greater constraint makes the grid an implicit DAG.

def longestIncreasingPath(matrix):
    m, n = len(matrix), len(matrix[0])
    memo = {}

    def dfs(r, c):
        if (r, c) in memo:
            return memo[(r, c)]
        best = 1
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]:
                best = max(best, 1 + dfs(nr, nc))
        memo[(r, c)] = best
        return best

    return max(dfs(r, c) for r in range(m) for c in range(n))

The strict inequality is load-bearing. Equal values would allow cycles, breaking memoization. The moment you see "strictly increasing" on a grid problem, that is the signal that memoized DFS is valid. Change it to "non-decreasing" and the approach falls apart entirely. One character separates a clean O(m*n) solution from an approach that does not terminate.

12. Word Search II (LC 212, Hard)

Running Word Search once per word is O(W * 4^L). Build a Trie from all words and walk it during DFS instead. All W words share the same traversal.

DFS from each cell, advancing a Trie node pointer alongside the grid position. If the current prefix has no children in the Trie, prune immediately. When you reach a word-end marker, record the word and remove it from the Trie to avoid duplicates and unlock further pruning.

The Trie prunes the DFS. Without it you backtrack after the full word length. With it you backtrack the moment the prefix diverges, cutting off potentially millions of recursive calls. This DFS-plus-auxiliary-structure combo appears whenever you need to match against many patterns simultaneously.

13. Critical Connections in a Network (LC 1192, Hard)

An edge (u, v) is a bridge if removing it disconnects the graph. Tarjan's algorithm finds all bridges in one DFS pass.

Each node gets two values: disc[v] (when it was discovered) and low[v] (the earliest discovery time reachable from v's subtree via back edges). After processing v's children, propagate low[u] = min(low[u], low[v]). Edge (u, v) is a bridge if low[w] > disc[v].

def criticalConnections(n, connections):
    graph = defaultdict(list)
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)
    disc = [-1] * n
    low = [0] * n
    timer = [0]
    result = []

    def dfs(v, parent):
        disc[v] = low[v] = timer[0]
        timer[0] += 1
        for w in graph[v]:
            if w == parent:
                continue
            if disc[w] == -1:
                dfs(w, v)
                low[v] = min(low[v], low[w])
                if low[w] > disc[v]:
                    result.append([v, w])
            else:
                low[v] = min(low[v], disc[w])

    dfs(0, -1)
    return result

low[w] > disc[v] is the entire condition. If w can reach an ancestor of v via any back edge, removing (v, w) does not disconnect the graph. If it cannot, that edge is the only path and qualifies as a bridge. This is the hardest problem on this list for legitimate reasons: the algorithm is non-trivial. But having done all twelve before, the two-array structure is at least recognizable as a pattern you have already trained.

The DFS Variants, One Per Problem

How the 13 DFS problems build on each other

Problem	DFS Variant Introduced
Max Depth	Postorder: aggregate upward
Number of Islands	Grid flood fill, outer loop for components
Path Sum	Preorder: pass state downward
Clone Graph	Hash map for graph cycles
Surrounded Regions	Inverse / boundary DFS
Course Schedule	3-color directed cycle detection
Word Search	Backtracking: mark then restore
Max Path Sum	Dual return plus global state
Pacific Atlantic	Multi-source reverse DFS
Serialize/Deserialize	Structural encoding via preorder
Longest Increasing Path	Memoized DFS on implicit DAG
Word Search II	DFS plus auxiliary Trie
Critical Connections	Tarjan's bridge algorithm

The second half of the list all require DFS combined with something else. A global variable, a reversed direction, an iterator-based deserializer, memoization, a Trie, or a pair of timestamp arrays. Once you notice this, the hard problems stop feeling like new ideas and start feeling like composites of things you already know.

What You Are Actually Training

Problems 1-4 cover the core variants: tree vs grid, bottom-up vs top-down, handling cycles. Problems 5-7 teach inverse reasoning, 3-color states, and the backtracking undo step. The final six pair DFS with a second technique.

The constraint in each problem signals which variant you need. Strictly increasing on a grid means memoizable DAG. Directed graph means 3-color. Word list means Trie. Undirected bridge question means Tarjan's disc and low arrays.

That pattern-to-constraint mapping is what separates candidates who name the approach immediately from candidates who rediscover it under interview pressure.

Recognizing Tarjan's algorithm before the interviewer finishes the problem statement

"When you call out disc and low arrays before the interviewer finishes reading the constraints."

Reading this list is one thing. Calling it out in real time, under a live interview clock, while narrating your reasoning is another. That gap is exactly what SpaceComplexity is built to close: voice-based mock interviews where the AI interviewer probes your DFS reasoning in real time, asking follow-up questions that reveal whether you understand the pattern or just memorized the code.