Get started

Depth-First Search Coding Problems: 50 Questions with Solutions

50 depth-first search coding problems — 1 easy · 41 medium · 8 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 7-day plan.

  • Problems: 50
  • By difficulty: 1 easy · 41 medium · 8 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

Depth-first search follows one path as far as it goes before backing up: recursion over a tree, flood fill over a grid, connected components over a graph, and the explicit stack that replaces recursion when depth is a concern. The problems here practise the visited bookkeeping, the base cases, and the choice between returning a value up the recursion and accumulating one in place.

How depth-first search works, step by step

A#1B#2C#5D#3E#4F#6emptycall stackdiscovery order: A B D E C F
Depth-first search from A, with the call stack drawn out. Example: edges = A–B, A–C, B–D, B–E, C–F, D–E; start = A
  1. Depth-first search follows one path as deep as it goes before trying another. dfs(A) is called: A is discovered 1st and pushed on the call stack.
  2. In dfs(A), B is unvisited, so dfs(B) is pushed on top and B is discovered 2nd. A's other neighbours wait until B's whole branch is finished.
  3. In dfs(B), D is unvisited, so dfs(D) is pushed on top and D is discovered 3rd. The stack always holds the path from A down to the node being explored.
  4. In dfs(D), E is unvisited, so dfs(E) is pushed on top and E is discovered 4th. The path is now A → B → D → E.
  5. E–B leads back to B, still on the stack: a back edge, which means the graph has a cycle, so it is not followed. Nothing unvisited is left around E: dfs(E) is popped and the search backtracks to D.
  6. Back in dfs(D), nothing unvisited is left: dfs(D) is popped and the search backtracks to B.
  7. Back in dfs(B), E is already finished (reached through D), so nothing unvisited is left: dfs(B) is popped and the search backtracks to A.
  8. Back in dfs(A), C is unvisited, so dfs(C) is pushed on top and C is discovered 5th. The search goes deep again from here.
  9. In dfs(C), F is unvisited, so dfs(F) is pushed on top and F is discovered 6th. That is every node found, but the open calls still have to return.
  10. F's only neighbour is C, its caller, so dfs(F) returns at once and the search backtracks to C.
  11. Back in dfs(C), nothing unvisited is left: dfs(C) is popped and the search backtracks to A.
  12. dfs(A) returns and the stack is empty. Discovery order: A, B, D, E, C, F; the teal edges are the calls made, the dashed one the back edge. Each node and edge is handled once: O(V + E).

Depth-First Search study plan

11 of the 50 Depth-First Search problems (1 easy, 7 medium and 3 hard) over 7 days, about 7 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 39 in the full list below are practice at your own pace. Then move on to Topological Sort.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.

Day 2

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 5

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Day 6

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Next topic: Topological Sort

Depth-First Search: the essentials

When to reach for it

Reachability, connected regions and properties of whole paths: count the islands, measure a region, decide whether a path exists, find a cycle in a directed graph. DFS does not give shortest paths in an unweighted graph, but it needs less bookkeeping than BFS, and its finishing order is what cycle detection and topological sorting rely on.

The pattern

Mark the node, then recurse into each unmarked neighbour. On a grid that may be modified, marking can mean overwriting the cell, land becoming water. Directed cycle detection needs three states, not two: unvisited, on the current path, and finished — reaching a node that is still on the current path closes a cycle.

def count_islands(grid):
    rows, cols = len(grid), len(grid[0])
    def sink(r, c):                 # 1 if (r, c) was unvisited land
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != 1:
            return 0
        grid[r][c] = 0              # mark before recursing
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            sink(r + dr, c + dc)
        return 1
    return sum(sink(r, c) for r in range(rows) for c in range(cols))

Cost

O(V + E) time. Space is the recursion depth, up to O(V) — a million frames on a 1000 × 1000 grid of land.

Common mistakes

  • Overflowing the call stack: Python stops at 1,000 frames by default, and other languages at whatever stack the process has. Use an explicit stack when depth can reach the input size.
  • Marking a node after the recursive calls instead of before, so two paths enter it.
  • One visited set for directed cycle detection, which mistakes a node finished on another branch for a cycle.
  • Forgetting to unmark when the question is about paths rather than reachability — that is Backtracking.

Start with

All depth-first search problems

Easy (1)

Medium (41)

Hard (8)

Companies that ask depth-first search problems

  • Amazon 45 problems on depth-first search
  • Google 43 problems on depth-first search
  • Microsoft 13 problems on depth-first search
  • Meta 12 problems on depth-first search
  • Adobe 3 problems on depth-first search
  • Bloomberg 2 problems on depth-first search
  • Flipkart 2 problems on depth-first search
  • Oracle 2 problems on depth-first search
  • Salesforce 2 problems on depth-first search
  • Uber 2 problems on depth-first search
  • Accenture 1 problem on depth-first search
  • Apple 1 problem on depth-first search

Next topic: Topological Sort