Skip to content

level 7 · Graphs

Depth-First Search

Plunge down one path to the end, then back up and try the next.

10 min 90 XP

what is it

Start here

Depth-first search is the opposite instinct to breadth-first. Instead of spreading out in careful rings, it commits: it picks a path and follows it as deep as it can go, only backing up when it hits a dead end.

The engine here is a stack instead of a queue. Newly found nodes go on top; you always take the node from the top. Because a stack is last-in-first-out, DFS always dives into the most recently discovered node — so it plunges deep before it ever goes wide. Watch the stack on the right grow tall as it descends, then shrink as it backtracks.

Both DFS and BFS visit every reachable node exactly once, and both cost the same. But the order is completely different, and that changes what they're good for. DFS is the natural fit for 'is there any path?', for exploring all possibilities (mazes, puzzles), and for detecting cycles.

One warning the visualization makes obvious: DFS is naturally recursive, and each level of depth sits on the call stack. On a huge graph, a plain recursive DFS can overflow that stack — which is exactly why the code here uses an explicit stack you can see.

real-life analogy

Picture it

Exploring a maze with one hand on the wall

You walk down a corridor as far as it goes. Dead end? You back up to the last junction and try the next corridor you hadn't taken. You fully exhaust one branch before considering another — that commitment to going deep is depth-first search.

interactive visualization

Watch it run

Pick a start node: 1 = A, up to 8 = H. Watch it dive deep first.

A
B
C
D
E
F
G
H

stack · LIFO

A

take from the top

Depth-first search plunges as deep as it can from A, using a stack. A stack is last-in-first-out, so it always dives into the most recently found node — that's why DFS goes deep before wide.

step 01/20

  • just discovered
  • visited
  • visiting now
1function dfs(graph, start) {
2 const stack = [start];
3 const seen = new Set([start]);
4 while (stack.length > 0) {
5 const node = stack.pop();
6 visit(node);
7 for (const next of graph[node]) {
8 if (!seen.has(next)) {
9 seen.add(next);
10 stack.push(next);
11 }
12 }
13 }
14}

variables right now

start
A
stack
A
comparisons 0moves 0

the dry run · every step, in words

20 steps

complexity

What it costs

best case
O(V + E)
average
O(V + E)
worst case
O(V + E)
extra memory
O(V)

Same cost as BFS: every node once, every edge once, so V + E. The space is the stack — O(V) in the worst case. With recursive DFS, that stack is the call stack, which is why very deep graphs can overflow it.

  • O(1)
  • O(log n)
  • O(n) · this one
  • O(n log n)
  • O(n²)
input size →work →

common mistakes

Common traps

  • Using a queue instead of a stack.

    A queue makes it explore in rings — that's BFS. DFS needs last-in-first-out so it dives into the newest node: a stack (or recursion).

  • Recursing on a huge graph without thinking about the call stack.

    Recursive DFS uses the call stack, and a very deep graph can overflow it. For deep graphs, use an explicit stack, like the code here does.

  • Not tracking visited nodes.

    Without a 'seen' set, a cycle sends DFS around forever. Mark nodes as you discover them, just like BFS.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+90 XP

01What data structure gives DFS its 'go deep first' behaviour?

02How do the nodes visited by DFS and BFS compare on the same graph?

03Why can a recursive DFS crash on a very deep graph?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.