Depth-First Search — Graph Algorithms

Overview

What this concept solves

Depth-First Search dives as deep as it can, then backs up. Start at a node. Pick the first child. Recurse. When you hit a dead-end — a node whose children are all visited — back up to the most recent node that still has unvisited children and continue. The trail you trace is a tree of 'first-time' edges, sometimes called the DFS tree.

Where BFS uses a queue and explores in rings, DFS uses a stack — usually the implicit call stack of recursion — and explores in branches. The single most important DFS concept is when you record each node relative to its children. On a tree the three answers form the three textbook traversal orders: Pre-order (N L R) records the node before descending; In-order (L N R) records it between the left and right recursion; Post-order (L R N) records it after both children are done. The recursion is the same — only the position of one record(node) line moves.

Those three orders unlock real work. Pre-order is how you copy or serialise a tree. In-order, on a binary search tree, comes out sorted. Post-order is how you delete a tree or compute any aggregate from the leaves up (compiler IR sizes, file-system disk usage, expression-tree evaluation). And the same DFS skeleton — generalised from a tree to a graph — is the engine behind cycle detection (a back edge to a still-grey ancestor), topological sort (reverse post-order on a DAG), connected components, Tarjan SCC, and every backtracking solver from sudoku to maze.

Mechanics

How it works

The three traversal orders, side by side

Pre-order (N L R) — record(node) is the first thing the function does after the null-check. You see every node before its children.
In-order (L N R) — record(node) sits between the recursive calls into left and right children. On a BST, this yields a sorted sequence.
Post-order (L R N) — record(node) is the last thing before the function returns. You see every node after both subtrees are fully done.
Reverse post-order of a DAG-DFS is exactly a topological sort. Same skeleton, same recursion — just a different prepend position.

Why the call stack matters

Each recursive call pushes a frame on the stack — that's the 'grey' set in textbook DFS.
While a frame is on the stack, its node is in progress — its children are being visited, but it isn't finished.
When the function returns, the frame pops — the node becomes 'black' (finished).
A back edge to a still-grey node = a cycle. Forward / cross edges to black nodes = same component, no cycle.

Recursion depth is a real problem

On a graph with a million nodes in a long path (think a linked list), recursive DFS blows the call stack. The fix is to write it iteratively with an explicit stack — same logic, no stack-overflow risk. Most production graph engines do this.

BFS vs DFS in one sentence

BFS asks 'who's nearby?' first — queue, level-order, shortest paths. DFS asks 'where does this go?' first — stack, recursion, structural questions. Same O(V + E) cost; entirely different output.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Depth-First Search

About this simulation

A nine-node binary tree walked recursively. The three tabs — Pre-order, In-order, Post-order — change when a node is recorded relative to its children; the rest of the DFS is identical. Use Step / Back to walk one call or return at a time.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Walk Pre-order (N L R)

Press Play in the Pre-order tab. Watch each node turn warning-orange the moment its frame is pushed — that's record(node) firing before either child is visited. The result row fills from the root downward. Result on this tree: F B A D C E G I H.

try 02

Walk In-order (L N R)

Switch to In-order. Now record() happens between left and right recursion — so a node only fires after its entire left subtree is done. On this tree (which is a BST when you read it left-to-right), the result comes out sorted: A B C D E F G H I.

try 03

Walk Post-order (L R N)

Switch to Post-order. The recording happens on the way back up — every node fires after both subtrees are done. Watch the call stack pop a frame just as the node turns orange. Result: A C E D B H I G F. Reverse this and you have one valid topological order of the tree.

try 04

Compare the three result strings

Run each mode through to completion and compare the Pre-order result / In-order result / Post-order result rows in your head. The recursion is identical — only the position of one line of code moves. That's the whole pedagogy of the three traversals in one prototype.

In practice

When to use it — and what you give up

When it's the right tool

Tree traversal — pre/in/post-order is DFS with record() in a different spot. Every tree walk is one of these three.
Cycle detection — the back-edge test fires the moment you see a grey-to-grey transition.
Topological sort — reverse post-order of a DAG-DFS is a valid topo order. No extra code needed.
Connected components — one DFS sweep from each unvisited node; everything it touches is one component.
Strongly connected components — Tarjan's and Kosaraju's algorithms are both two DFS passes with light bookkeeping.
Backtracking problems — maze solving, sudoku, N-queens, generating permutations. 'Undo on failure' is just popping the recursion stack.

When to reach for something else

Shortest path in an unweighted graph — use BFS. DFS doesn't track distances and will happily report a long path before the short one.
Weighted shortest path — use Dijkstra. DFS visit-order has nothing to do with cost.
Very deep graphs — write DFS iteratively or use BFS; recursive DFS overflows the call stack at a few hundred thousand nodes.

Pros

Linear time — O(V + E), same as BFS. Visits every node and edge once.
One function, three orders — pre/in/post-order all share the recursion, differing only by where record() sits.
Discovers structure — tree edges, back edges, discovery/finish times — the inputs to Tarjan SCC, articulation points, bridges.
Low memory on narrow graphs — only needs to remember the current path: O(depth) instead of O(width).
The native shape of backtracking — try a choice, recurse, undo on failure. Every backtracking solver is DFS in disguise.

Cons

No shortest-path guarantee — DFS can find any path before the shortest one. Use BFS or Dijkstra if distance matters.
Stack overflow on deep graphs — recursive form fails at ~1e5 nodes deep in many runtimes; switch to an explicit stack.
Visit order depends on child order — same tree stored differently produces different traversals. Surprising for tests.
Pre/in/post are tree concepts — on general graphs you only get pre-order (discovery time) and post-order (finish time); in-order needs a notion of 'middle child' which only exists on binary trees.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

dfs-tree-traversal.ts

// Recursive DFS — pre/in/post-order on a binary tree.
type Node = { val: string; left: Node | null; right: Node | null };

function preorder(node: Node | null, out: string[] = []): string[] {
  if (!node) return out;
  out.push(node.val);                  // ← N (before children)
  preorder(node.left, out);            //   L
  preorder(node.right, out);           //   R
  return out;
}

function inorder(node: Node | null, out: string[] = []): string[] {
  if (!node) return out;
  inorder(node.left, out);             //   L
  out.push(node.val);                  // ← N (between children) — sorted on a BST
  inorder(node.right, out);            //   R
  return out;
}

function postorder(node: Node | null, out: string[] = []): string[] {
  if (!node) return out;
  postorder(node.left, out);           //   L
  postorder(node.right, out);          //   R
  out.push(node.val);                  // ← N (after both children done)
  return out;
}

// Generalised to a graph: pre-order = discovery time, post-order = finish time.
// Reverse post-order of a DAG-DFS is a topological sort.

References & further reading

6 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

What is the only difference between pre-order, in-order, and post-order DFS on a binary tree?

question 02 / 03

Using the white-grey-black classification on a graph DFS, what indicates a cycle?

question 03 / 03

Why does in-order DFS on a binary search tree (BST) produce a sorted sequence?

0/3 answered