# Depth-First Search

> Explore everything reachable from a start by going as deep as possible before backing up. The visited set, the call stack, and where depth-first search is the right tool.

- Track: DSA (Concepts)
- Level: Beginner
- Format: Step-through player
- Author: Aayush Ostwal
- Published: 26 October 2026
- Topics: Graphs, DFS, Recursion
- Canonical URL: https://compoundengineer.com/library/dsa/depth-first-search

Concept · Graph traversal

Beginner · O(V + E) time · O(V) space

## Why it exists

You are in one room of a building with many doors, and you want to know which rooms you can reach. Walking through doors at random fails in two ways: you miss rooms, and if some doors lead back to rooms you have already seen, you walk in circles forever.

We need a method that visits every reachable room exactly once and always stops. How do we explore without repeating ourselves and without forgetting where to go back to?

## The core idea

Two rules do it. First, keep a set of visited nodes and never enter one twice. Second, from the current node, pick a neighbour you have not visited and go there at once. Keep going deeper. When a node has no new neighbours, you are at a dead end: go back to where you came from and try its next neighbour.

Go as deep as you can. At a dead end, back up one step and try the next option.

The "back up" part needs no extra data: if the search is a recursive function, the call stack remembers where you came from. This is called depth-first search , or DFS.

## A worked example

Six links join seven nodes. Nodes 0, 1, 2 and 3 form a loop, node 4 hangs off node 3, and nodes 5 and 6 are connected only to each other. The search starts at node 0.

Going deep. From node 0 the first neighbour is 1, then from 1 the first new neighbour is 3. The search is three calls deep, and each call waits for the one below it.

The loop. At node 3 the neighbour 1 is already visited, so it is skipped. That check is what stops the loop 0–1–3–2 from running forever. The next neighbour, 2, is new.

Dead ends. At node 2 both neighbours (0 and 3) are visited, so node 2 is finished and the search returns to node 3. Node 3 still has a neighbour left, node 4. Node 4 is a dead end too.

What it never reaches. The result is [0, 1, 3, 2, 4] . Nodes 5 and 6 are not in it, because no path leads to them from node 0. DFS finds exactly the nodes reachable from the start.

## How it works

- Mark the current node visited and record it.

- For each neighbour: not visited yet⟶search from it

- When the loop ends, return to the caller. That is the "back up" step.

- To cover a graph in several pieces, start a new search from every node that is still unvisited.

### Why it is correct

Every node is visited at most once, because we mark it on entry and never enter a visited node. Every reachable node is visited: if a node is reachable, some path leads to it, and along that path each node gets visited, so it hands the search to the next. The search cannot stop while a visited node still has an unvisited neighbour.

## Watch it run

Pick an input, then press Play or use the arrow keys. The highlighted line is the one running, and the number beside each line counts how often it ran. The call stack shows where the search will return to. Teal nodes are on the current path, grey nodes are finished, and the green links are the ones the search walked.

## Complexity

O(V + E)

Time. Here's why: each node is entered once, which is V calls. Each link is looked at once from each end, which is 2E checks of O(1) each. The total is V + 2E.

O(V)

Space. The visited set holds up to V nodes. The call stack is as deep as the longest path the search follows, up to V. The adjacency lists, which belong to the input, hold V + 2E entries.

## Mistakes and variants

- Marking too late. If you mark a node when you leave it instead of when you enter it, a cycle sends you back in before the mark is made, and the search never ends.

- Deep recursion. A graph that is one long path makes the recursion V calls deep. Python stops at about 1000 by default. Replace the recursion with your own stack: push the start, then repeatedly pop a node and push its unvisited neighbours. The order of visiting can differ, but the set of visited nodes is the same.

- DFS is not shortest path. The route DFS finds to a node is whichever one it tried first. For fewest steps use breadth-first search. For cheapest cost use Dijkstra.

- On a grid. The neighbours of cell (r, c) are its four sides, and each must be checked against the edges of the grid before the visited check.

- Asking a yes-or-no question. Many problems fix a rule for which neighbours are allowed, such as "cells at most t high", and ask whether the end can be reached. DFS answers that in one pass.

## Where it shows up

Reach for it when:

- the question is "what can I reach?" or "can I get from A to B?", and the cost of the route does not matter;

- you need to count or label the connected pieces of a graph or a grid;

- you must try every option and undo the last choice at a dead end (backtracking is DFS on a tree of choices).

Problems that use it:

- Swim in Rising Water (as the reachability check inside a binary search)

- Critical Connections in a Network (one DFS, with extra numbers per node)

- Number of Islands (the same flood fill, with a queue instead of recursion)

- Word Search (DFS that marks a cell and undoes the mark)

## Interviewer follow-ups

These are the questions that usually come next. Open one to see an answer you could say out loud.

"This graph is one chain of a million nodes. Does it run?"

What they are checking Whether you know that a correct recursive search can still crash, and whether you can fix it without changing the idea.

A strong answer No. The recursion would be a million calls deep, and Python's default limit is around 1000. Other languages can overflow the call stack too. I would keep my own stack: push the start, then pop a node, mark it, and push its unvisited neighbours. Time and space stay O(V + E).

"Would you use DFS or BFS to find the fewest steps between two nodes?"

What they are checking Whether you choose the traversal because of what it guarantees, not by habit.

A strong answer BFS. It visits nodes in order of distance, so the first time it reaches the target it has used the fewest steps. DFS reaches the target by whichever path it tried first, which can be much longer. If the steps have different costs, neither works and I would use Dijkstra.

"How would you use this to detect a cycle?"

What they are checking Whether you can adapt the visited check, and whether you notice that directed and undirected graphs differ.

A strong answer In an undirected graph, a neighbour that is already visited and is not the node I came from means a cycle. In a directed graph that is not enough, because two paths can meet without forming a cycle. There I keep three states for each node: not seen, on the current path, and finished. A cycle exists exactly when I reach a node that is on the current path.

## Solution code

### Python

```python
class DepthFirstSearch:
    def order(self, n, edges, start):
        self.graph = [[] for _ in range(n)]
        for u, v in edges:
            self.graph[u].append(v)
            self.graph[v].append(u)
        self.visited = set()
        self.result = []
        self.dfs(start)
        return self.result

    def dfs(self, node):
        self.visited.add(node)  # mark on entry
        self.result.append(node)
        for nxt in self.graph[node]:
            if nxt not in self.visited:
                self.dfs(nxt)
`.replace(/^\n/, '');

function solve(n, edges, start) {
  const g = Array.from({ length: n }, () => []);
  edges.forEach(([u, v]) => { g[u].push(v); g[v].push(u); });
  const seen = new Set(), order = [];
  (function dfs(u) { seen.add(u); order.push(u); for (const v of g[u]) if (!seen.has(v)) dfs(v); })(start);
  return order;
}

function traceDfs(T, n, edgesIn, start) {
  const pos = POS[n];
  const nodes = [...Array(n).keys()].map(i => pos ? { id: i, x: pos[i][0], y: pos[i][1] } : { id: i });
  const edges = edgesIn.map(([u, v]) => ({ u, v }));
  const adj = Array.from({ length: n }, () => []);
  edgesIn.forEach(([u, v]) => { adj[u].push(v); adj[v].push(u); });
  const ekey = (a, b) => { const e = edges.find(e => (e.u === a && e.v === b) || (e.u === b && e.v === a)); return `${e.u}-${e.v}
```

---
From Compound Engineer (https://compoundengineer.com), visual lessons for engineers. The page above is the full interactive version.