mergedengineering
Back to Data Structures and Algorithms

Depth-First Search (DFS) Complete Guide

Algorithm • medium

DFS dives **as deep as possible** down each branch before backtracking. Implementation is either recursion (most natural) or an explicit stack.

It's the algorithmic shape behind cycle detection, topological sort, connected-component finding, maze-solving, and most backtracking problems.

Like BFS, it's O(V + E) but its memory profile is O(depth) on the call stack, often dramatically less than BFS's O(V) queue.

Typical Complexity Baseline

MetricValue
TimeO(V + E)
SpaceO(V) recursion depth

See It

Concept Diagram

A small animated SVG that illustrates the core idea the moving parts you need to keep in your head when you read the rest of the guide.

DFS go deep, then back up

We follow one branch all the way down before returning to try a sibling.

go deep first · backtrack on dead endsSABCDEFGHIstack:[S]order:[S]
Step 1/20Start at S. Mark visited. Stack = [S].

Watch First

Video Explainer

A quick visual walkthrough before the detailed sections pick the format that helps you learn fastest.

Mechanics

Core Concepts

The building blocks and terminology you need before everything else clicks. Skim or deep-read.

Recursion (or stack)

What it is The call stack acts as the implicit data structure. Each frame is a partial walk through the graph.

Why it matters Recursion (or stack) is a required building block for understanding how Depth-First Search (DFS) stays correct and performant on large inputs.

Visited set

What it is Without it, DFS on a graph with cycles loops forever. Trees don't need it; graphs do.

Why it matters Visited set is a required building block for understanding how Depth-First Search (DFS) stays correct and performant on large inputs.

Pre/post hooks

What it is Logic that runs when entering vs. leaving a node. Post-order is where topological sort and tree-DP happen.

Why it matters Pre/post hooks is a required building block for understanding how Depth-First Search (DFS) stays correct and performant on large inputs.

3-color marking

What it is white = unvisited, gray = on current DFS path, black = fully explored. A gray-to-gray edge is a back-edge a cycle.

Why it matters 3-color marking is a required building block for understanding how Depth-First Search (DFS) stays correct and performant on large inputs.

Backtrack step

What it is When a node has no more unvisited neighbors, undo any state changes and return to the parent frame.

Why it matters Backtrack step is a required building block for understanding how Depth-First Search (DFS) stays correct and performant on large inputs.

Preorder

What it is Process the node before its children. Used for serializing trees, copying structure.

Why it matters Process the node before its children. Used for serializing trees, copying structure. In Depth-First Search (DFS), this definition helps you reason about correctness and complexity when inputs scale.

Postorder

What it is Process the node after all children. Used for tree DP, deletion, and topological sort.

Why it matters Process the node after all children. Used for tree DP, deletion, and topological sort. In Depth-First Search (DFS), this definition helps you reason about correctness and complexity when inputs scale.

Back edge

What it is An edge from a descendant to an ancestor in the DFS tree its existence proves a cycle.

Why it matters An edge from a descendant to an ancestor in the DFS tree its existence proves a cycle. In Depth-First Search (DFS), this definition helps you reason about correctness and complexity when inputs scale.

DFS tree

What it is The implicit tree formed by the parent pointers in DFS. Subtree size = nodes reachable through that branch.

Why it matters The implicit tree formed by the parent pointers in DFS. Subtree size = nodes reachable through that branch. In Depth-First Search (DFS), this definition helps you reason about correctness and complexity when inputs scale.

Iterative DFS

What it is Same algorithm with an explicit stack. Useful when recursion depth would blow the default stack limit (~10⁴ in Python).

Why it matters Same algorithm with an explicit stack. Useful when recursion depth would blow the default stack limit (~10⁴ in Python). In Depth-First Search (DFS), this definition helps you reason about correctness and complexity when inputs scale.

Walkthrough

Putting It All Together

Every frame of the concept diagram, laid out top-to-bottom so you can scroll through the algorithm at your own pace.

Step 1/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[S]order:[S]

Start at S. Mark visited. Stack = [S].

Step 2/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[S, A]order:[S, A]

From S, push A (unvisited). Visit A.

Step 3/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[S, A, B]order:[S, A, B]

From A, push B (unvisited). Visit B.

Step 4/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[S, A, B, C]order:[S, A, B, C]

From B, push C (unvisited). Visit C.

Step 5/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[S, A, B, C, D]order:[S, A, B, C, D]

From C, push D (unvisited). Visit D.

Step 6/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[S, A, B, C, D, I]order:[S, A, B, C, D, I]

From D, push I (unvisited). Visit I.

Step 7/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[S, A, B, C, D]order:[S, A, B, C, D, I]

I has no more unvisited children → pop. Back to D.

Step 8/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[S, A, B, C]order:[S, A, B, C, D, I]

D has no more unvisited children → pop. Back to C.

Step 9/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[S, A, B]order:[S, A, B, C, D, I]

C has no more unvisited children → pop. Back to B.

Step 10/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[S, A, B, G]order:[S, A, B, C, D, I, G]

From B, push G (unvisited). Visit G.

Step 11/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[S, A, B]order:[S, A, B, C, D, I, G]

G has no more unvisited children → pop. Back to B.

Step 12/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[S, A]order:[S, A, B, C, D, I, G]

B has no more unvisited children → pop. Back to A.

Step 13/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[S, A, E]order:[S, A, B, C, D, I, G, E]

From A, push E (unvisited). Visit E.

Step 14/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[S, A, E, H]order:[S, A, B, C, D, I, G, E, H]

From E, push H (unvisited). Visit H.

Step 15/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[S, A, E]order:[S, A, B, C, D, I, G, E, H]

H has no more unvisited children → pop. Back to E.

Step 16/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[S, A]order:[S, A, B, C, D, I, G, E, H]

E has no more unvisited children → pop. Back to A.

Step 17/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[S]order:[S, A, B, C, D, I, G, E, H]

A has no more unvisited children → pop. Back to S.

Step 18/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[S, F]order:[S, A, B, C, D, I, G, E, H, F]

From S, push F (unvisited). Visit F.

Step 19/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[S]order:[S, A, B, C, D, I, G, E, H, F]

F has no more unvisited children → pop. Back to S.

Step 20/20
go deep first · backtrack on dead endsSABCDEFGHIstack:[]order:[S, A, B, C, D, I, G, E, H, F]

S has no more unvisited children → pop. Stack empty → done.

Tradeoffs

How It Compares

When this technique wins, when it loses, and what to reach for instead.

vs. Breadth-First Search (BFS)

Choose this when Choose DFS when you need cycle detection, topological order, or any tree-shaped exploration. Also when memory is tight and the graph is deep but narrow.

Tradeoff DFS does **not** find shortest paths. The first time DFS reaches a node is generally not via the shortest path.

vs. Iterative deepening DFS

Choose this when Plain DFS when you don't care about depth.

Tradeoff IDDFS uses BFS-style optimal-depth guarantees with DFS's memory profile but at the cost of repeated work.

vs. Backtracking

Choose this when DFS when you're exploring a graph; backtracking when you're exploring a constraint search tree.

Tradeoff Backtracking is essentially DFS plus 'undo step on return' for state same shape, different bookkeeping.

In Production

Real-World Stories

Where this shows up at real companies and what the on-call engineer learned the hard way.

Build systems (Bazel, Make, Webpack)

Every modern build system runs DFS over a dependency DAG to compute the topological build order and uses gray/black marking to fail fast on circular dependencies.

Takeaway Cycle detection in build graphs is mission-critical; DFS makes it nearly free.

Programming language compilers

Type-checkers, lint rules, and dead-code-elimination passes traverse ASTs with recursive DFS. The post-order step is where most analysis happens (children analyzed before parent).

Takeaway Trees and ASTs are DFS's natural habitat postorder lets information flow up.

Filesystem tools (find, du, rsync)

Recursive directory traversal is DFS. du (disk usage) is post-order DFS totaling subtree sizes only after children are fully measured.

Takeaway Tree-shaped problems with bottom-up aggregation map directly to post-order DFS.

Code

Implementation

A clean reference implementation in TypeScript, Python, and Go. Switch languages with the toggle.

Standard recursive DFS that returns the visited set in DFS-finish order useful for topological sort and component labeling.

Complexity: Time O(V + E), Space O(V) call stack + visited

Recursive DFS with cycle-safe visited tracking

function depthFirstSearch(params: {
  sourceNode: string
  adjacencyByNode: Map<string, string[]>
}): string[] {
  const visitedNodes = new Set<string>()
  const dfsFinishOrder: string[] = []

  function visitNode(currentNode: string): void {
    if (visitedNodes.has(currentNode)) return
    visitedNodes.add(currentNode)
    for (const neighborNode of params.adjacencyByNode.get(currentNode) ?? []) {
      visitNode(neighborNode)
    }
    dfsFinishOrder.push(currentNode)
  }

  visitNode(params.sourceNode)
  return dfsFinishOrder
}

Watch Out

Common Problems and Failure Modes

The bugs and edge cases that bite engineers most often. Skim before you ship.

  • Recursion depth exceeding the language's stack limit (Python ~10⁴, JVM ~10⁴–10⁵). Convert to iterative DFS for deep graphs.
  • Forgetting the visited set on graphs with cycles infinite loop guaranteed.
  • Using preorder when postorder is needed (or vice versa) silent bug, wrong answer.
  • Mutating shared state in the recursive call without undoing it on backtrack every problem in the 'permutations / N-queens' family has this trap.
  • Confusing DFS-tree edges with original graph edges when reasoning about back edges.

Pro Tips

Tips and Tricks

Small habits that pay off every time you reach for this pattern.

  • Start by writing the core invariant in one sentence before coding.
  • Test empty, single-item, and duplicate-heavy inputs early.
  • Pick the pattern first (map, pointers, recursion, heap, etc.), then implement details.
  • Track both time and space complexity while iterating on correctness.

Pattern Recognition

When to Use

Concrete signals that tell you this is the right pattern both at work and on LeetCode.

Real-system usage signals

  • Detecting cycles in directed graphs (via 3-color DFS: white / gray / black).
  • Topological sorting the post-order DFS finish order, reversed, is a valid topo order.
  • Counting and labeling connected components in undirected graphs.
  • Backtracking problems: permutations, combinations, N-queens, Sudoku all are DFS through a search tree.
  • Tree traversals (preorder/inorder/postorder are all DFS variants).
  • Bridge and articulation point detection (Tarjan's algorithm).

LeetCode-specific tips (pattern-identification signals)

  • Identification signal: focus on verbs like optimize, order, schedule, traverse, or shortest path; these often indicate algorithm-first problems.
  • Identification signal: if brute force is easy to write but constraints are large, you likely need a known algorithmic pattern.
  • Map the prompt to pattern families first (search, traversal, greedy, DP, graph) before coding details.
  • For Depth-First Search (DFS) questions, start by naming the core invariant before writing code.
  • Use the constraint section to set time/space target first, then pick the data structure/algorithm.
  • Solve one tiny example by hand and map each transition to your variables before implementing.
  • Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
  • During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.

Practice

LeetCode Progression

A curated easy-to-hard problem ladder. Each one reinforces a specific aspect of the pattern.

#ProblemDifficultyTypical Complexity
1Number of IslandsMediumO(rows × cols)
2Clone GraphMediumO(V + E)
3Course ScheduleMediumO(V + E), cycle detection
4Pacific Atlantic Water FlowMediumO(rows × cols)
5Path Sum IIMediumO(n)
6Word SearchMediumO(rows × cols × 4^len)
7Critical Connections in a NetworkHardO(V + E), Tarjan's bridges
8Longest Increasing Path in a MatrixHardO(rows × cols), DFS + memo