Depth-First Search Interview Pattern: When to Use It and 5 Problems to Practice (2026)

When an interview asks you to explore every possible route, count distinct regions, or generate all configurations, the depth‑first search (DFS) pattern is often the right tool. At its core, DFS walks a structure (graph, tree, or grid) by diving as deep as possible along one branch before backtracking. This "go‑deep‑then‑backtrack" mindset matches many classic interview prompts.

Recognizing the DFS Signal

If the problem mentions all solutions, connected structures, or exponential possibilities, start thinking DFS. BFS is the alternative when you need the shortest path or level‑by‑level processing.

A Worked Example: "Number of Islands"

Problem: Given a 2‑D grid of '1' (land) and '0' (water), count how many distinct islands exist. Islands are groups of adjacent '1' cells (horizontal/vertical).

Idea: Treat each '1' as a node in a graph where edges connect neighboring cells. When you encounter an unvisited '1', launch a DFS to mark the whole island, then increment the count.

Python implementation:

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    visited = [[False] * cols for _ in range(rows)]

    def dfs(r, c):
        # boundary and water checks
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] == '0' or visited[r][c]:
            return
        visited[r][c] = True
        # explore four directions
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)

    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and not visited[r][c]:
                dfs(r, c)
                islands += 1
    return islands

Complexity: Each cell is visited at most once, so time is O(R·C) and space is O(R·C) for the visited matrix (or O(min(R·C, recursion depth)) if you mutate the grid in‑place).

Common Pitfalls and How to Avoid Them

1. Missing visited tracking – Without a visited set or in‑place marking, you’ll revisit the same node and explode exponentially.
2. Stack overflow on deep recursion – Large grids or deep trees can exceed Python’s recursion limit. Switch to an explicit stack (list) if you anticipate >10⁴ depth.
3. Wrong neighbor definition – The problem may allow diagonal moves; always verify the adjacency rules.
4. Modifying the input unintentionally – Some platforms forbid mutating the argument. Use a separate visited matrix if you need to preserve the original.
5. Confusing DFS with backtracking – Backtracking adds the step of undoing a choice (e.g., removing a queen from a board). Pure DFS for counting components does not need undo logic.

Five Representative Practice Problems

1. "Word Search"

Prompt: Given a board of letters and a word, determine if the word can be formed by sequentially adjacent cells (horizontal/vertical). Each cell may be used only once per word. Hint: Treat each cell as a node; perform DFS from cells matching the first character, marking visited cells along the path.

2. "Clone Graph"

Prompt: Given a reference to a node in an undirected graph, return a deep copy of the entire graph. Hint: Use DFS (recursive or stack) to traverse nodes, storing a map from original to cloned node to avoid duplicating.

3. "Generate Parentheses"

Prompt: Produce all valid combinations of n pairs of parentheses. Hint: Model the generation as a decision tree where each step adds '(' or ')' respecting balance; DFS explores each branch fully before backtracking.

4. "Binary Tree Paths"

Prompt: Return all root‑to‑leaf paths as strings like "1->2->5". Hint: Perform a DFS that carries the current path; when you hit a leaf, append the path to the result list.

5. "Maximum Area of Island"

Prompt: Similar to "Number of Islands" but you need the size of the largest island. Hint: During DFS, keep a counter for the current island's cells; compare it to a global maximum after each DFS completes.

Each of these problems forces you to manage recursion depth, visited state, and backtracking logic—exactly the skills DFS interviews test.

Complexity Cheat Sheet

When NOT to Use DFS

• Shortest‑path requirement – BFS guarantees minimal steps; DFS may find a longer route first.
• Level‑order processing – If the problem asks for "nodes at distance k", BFS aligns naturally.
• Memory‑constrained environments – Recursive DFS can blow the call stack; an iterative approach or BFS with a queue may be safer.

How to Practice This

1. Pick a problem, write the DFS skeleton – Start with a function that marks a node visited and recurses into neighbors. Fill in the specifics later.
2. Run the solution against edge cases – Empty inputs, single‑node graphs, and highly unbalanced trees often reveal missing visited checks.
3. Use Call Assistant to rehearse – Explain your approach aloud while the assistant captures your answer, then iterate on feedback to tighten the narrative.

---

FAQ

• Q: How do I decide between recursive and iterative DFS? A: Use recursion when the depth is modest and the language handles stack frames comfortably. Switch to an explicit stack if the input can be very deep or if you need more control over memory.

• Q: Can DFS be used on directed graphs? A: Yes. For directed graphs, DFS respects edge direction, which is useful for cycle detection and topological sorting.

• Q: What’s the difference between DFS for counting components vs. backtracking? A: Counting components only needs to mark visited nodes; backtracking also undoes choices (e.g., removing a queen) to explore alternative configurations.

• Q: Why do many solutions mutate the input grid instead of using a visited matrix? A: Mutating in‑place saves O(R·C) extra space, but it’s only safe when the problem statement permits modifying the input.