Depth-First Search (DFS) Explained Step by Step — With Code Examples
DFS is one of the two fundamental graph/tree traversal algorithms. It goes as deep as possible before backtracking — like exploring a maze by always taking the first path until you hit a dead end, then backtracking to try another route. This guide covers the three DFS traversal orders for trees, recursive and iterative implementations, graph DFS with cycle detection, classic interview problems (max depth, number of islands, path sum, topological sort), and when to use DFS vs BFS.
O(V+E)
time — visits all vertices and edges exactly once
O(V)
space — call stack depth or explicit stack size
Stack
DFS uses a stack — implicit (call stack) or explicit
Pre/In/Post
3 tree traversal orders with distinct use cases
1
The Core Idea — How DFS Works
The DFS mental model
DFS explores as far as possible along each branch before backtracking. Think of it as reading a book chapter-by-chapter (depth — finish chapter 1 completely), vs skimming all chapter titles first (breadth). DFS uses a stack; BFS uses a queue. In recursive DFS, the call stack IS the stack.
1
Start at root (or any node)
Mark the starting node as visited. Add it to the result or process it.
2
Explore the first unvisited neighbor
Recursively call DFS on the first unvisited child/neighbor. Go as deep as possible down this branch.
3
When dead end reached, backtrack
Return to parent node (function returns from recursive call). Explore the next unvisited child/neighbor.
4
Repeat until all nodes visited
Every vertex is visited exactly once, in DFS order. For disconnected graphs: restart from each unvisited node to reach all components.
2
DFS on Binary Tree — 3 Traversal Orders
| Item | Traversal Order | When Root is Visited / Best Use Case |
|---|---|---|
| Pre-order (NLR) | Root → Left → Right. Root visited BEFORE its children. | Copy a tree structure, serialize tree to array, prefix expressions |
| In-order (LNR) | Left → Root → Right. Root visited BETWEEN children. | BST: produces nodes in sorted ascending order. Validate BST. |
| Post-order (LRN) | Left → Right → Root. Root visited AFTER all children. | Delete tree (delete children before parent), calculate directory sizes, postfix expressions |
javascriptTree DFS — All Three Orders (Recursive and Iterative)
// ─── Recursive implementations ────────────────────────────────────────────────
function preOrder(node, result = []) {
if (!node) return result;
result.push(node.val); // 1. Visit root FIRST
preOrder(node.left, result); // 2. Go left
preOrder(node.right, result); // 3. Go right
return result;
}
function inOrder(node, result = []) {
if (!node) return result;
inOrder(node.left, result); // 1. Go left
result.push(node.val); // 2. Visit root IN MIDDLE
inOrder(node.right, result); // 3. Go right
return result;
}
function postOrder(node, result = []) {
if (!node) return result;
postOrder(node.left, result); // 1. Go left
postOrder(node.right, result); // 2. Go right
result.push(node.val); // 3. Visit root LAST
return result;
}
// For a BST with nodes [4, 2, 6, 1, 3, 5, 7]:
// 4
// / \
// 2 6
// / \ / \
// 1 3 5 7
// Pre-order: [4, 2, 1, 3, 6, 5, 7] ← root first, great for copying
// In-order: [1, 2, 3, 4, 5, 6, 7] ← sorted! BST property
// Post-order: [1, 3, 2, 5, 7, 6, 4] ← root last, great for deletion
// ─── Iterative In-Order (avoids call stack overflow on deep trees) ─────────────
function inOrderIterative(root) {
const result = [];
const stack = [];
let current = root;
while (current || stack.length > 0) {
// Go as far left as possible, pushing nodes to stack
while (current) {
stack.push(current);
current = current.left;
}
// Pop and visit
current = stack.pop();
result.push(current.val);
// Move to right subtree
current = current.right;
}
return result;
}
// ─── Iterative Pre-Order ──────────────────────────────────────────────────────
function preOrderIterative(root) {
if (!root) return [];
const result = [];
const stack = [root];
while (stack.length > 0) {
const node = stack.pop();
result.push(node.val);
// Push right first so left is processed first (LIFO)
if (node.right) stack.push(node.right);
if (node.left) stack.push(node.left);
}
return result;
}3
DFS on a Graph — Recursive and Iterative
Graphs (unlike trees) can have cycles. You need a visited set to avoid infinite loops. For disconnected graphs, run DFS from every unvisited node.
javascriptGraph DFS — Recursive and Iterative
const graph = {
A: ['B', 'C'],
B: ['A', 'D', 'E'],
C: ['A', 'F'],
D: ['B'],
E: ['B', 'F'],
F: ['C', 'E']
};
// ─── Recursive DFS ────────────────────────────────────────────────────────────
function dfsRecursive(graph, start) {
const visited = new Set();
const result = [];
function explore(node) {
if (visited.has(node)) return;
visited.add(node);
result.push(node);
for (const neighbor of graph[node] || []) {
explore(neighbor); // recurse into each unvisited neighbor
}
}
explore(start);
return result;
}
dfsRecursive(graph, 'A'); // → ['A', 'B', 'D', 'E', 'F', 'C']
// ─── Iterative DFS (explicit stack — safe for deep graphs) ────────────────────
function dfsIterative(graph, start) {
const visited = new Set();
const stack = [start];
const result = [];
while (stack.length > 0) {
const node = stack.pop(); // LIFO — stack (not queue like BFS)
if (visited.has(node)) continue;
visited.add(node);
result.push(node);
// Push neighbors in reverse to maintain same left-to-right order as recursive
const neighbors = graph[node] || [];
for (let i = neighbors.length - 1; i >= 0; i--) {
if (!visited.has(neighbors[i])) {
stack.push(neighbors[i]);
}
}
}
return result;
}
// ─── All Connected Components (disconnected graph) ────────────────────────────
function allComponents(graph) {
const visited = new Set();
const components = [];
for (const node of Object.keys(graph)) {
if (!visited.has(node)) {
const component = [];
// DFS from this unvisited node finds one complete component
function explore(n) {
if (visited.has(n)) return;
visited.add(n);
component.push(n);
for (const nb of graph[n] || []) explore(nb);
}
explore(node);
components.push(component);
}
}
return components; // each inner array = one connected component
}4
Classic DFS Interview Problems
javascriptMax depth, path sum, and cycle detection
// ─── Maximum Depth of Binary Tree — LeetCode #104 ────────────────────────────
function maxDepth(root) {
if (!root) return 0;
// Depth at this node = 1 + deeper of the two subtrees
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
// ─── Path Sum — LeetCode #112 ────────────────────────────────────────────────
// Does any root-to-leaf path sum equal target?
function hasPathSum(root, targetSum) {
if (!root) return false;
const remaining = targetSum - root.val;
if (!root.left && !root.right) return remaining === 0; // leaf node check
return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
}
// ─── All Root-to-Leaf Paths — LeetCode #257 ──────────────────────────────────
function binaryTreePaths(root) {
const paths = [];
function dfs(node, currentPath) {
if (!node) return;
currentPath.push(node.val);
if (!node.left && !node.right) {
paths.push([...currentPath].join('->')); // found a leaf — record path
}
dfs(node.left, currentPath);
dfs(node.right, currentPath);
currentPath.pop(); // backtrack — remove current node before returning
}
dfs(root, []);
return paths;
}
// ─── Detect Cycle in Directed Graph ──────────────────────────────────────────
// Uses 3-color marking: white (unvisited), gray (in current path), black (done)
function hasCycle(graph) {
const WHITE = 0, GRAY = 1, BLACK = 2;
const color = {};
for (const node of Object.keys(graph)) color[node] = WHITE;
function dfs(node) {
color[node] = GRAY; // Mark as "in progress" on current path
for (const neighbor of graph[node] || []) {
if (color[neighbor] === GRAY) return true; // Back edge = cycle!
if (color[neighbor] === WHITE && dfs(neighbor)) return true;
}
color[node] = BLACK; // Mark as "fully explored"
return false;
}
for (const node of Object.keys(graph)) {
if (color[node] === WHITE && dfs(node)) return true;
}
return false;
}javascriptNumber of Islands and Topological Sort
// ─── Number of Islands — LeetCode #200 (Grid DFS) ────────────────────────────
function numIslands(grid) {
if (!grid.length) return 0;
let count = 0;
const rows = grid.length, cols = grid[0].length;
function dfs(r, c) {
// Out of bounds or water or already visited — stop
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') return;
grid[r][c] = '0'; // "sink" the island cell to mark as visited
// Explore all 4 directions
dfs(r + 1, c); dfs(r - 1, c);
dfs(r, c + 1); dfs(r, c - 1);
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === '1') {
count++;
dfs(r, c); // sink the entire connected island
}
}
}
return count;
}
// ─── Topological Sort — Course Schedule ──────────────────────────────────────
// Given prerequisites: [[1,0], [2,0], [3,1], [3,2]]
// (course 1 requires course 0, etc.)
function canFinish(numCourses, prerequisites) {
const graph = Array.from({length: numCourses}, () => []);
for (const [course, prereq] of prerequisites) {
graph[prereq].push(course);
}
const UNVISITED = 0, VISITING = 1, VISITED = 2;
const state = new Array(numCourses).fill(UNVISITED);
function dfs(node) {
if (state[node] === VISITING) return false; // cycle detected
if (state[node] === VISITED) return true; // already processed
state[node] = VISITING;
for (const neighbor of graph[node]) {
if (!dfs(neighbor)) return false;
}
state[node] = VISITED;
return true;
}
// Check every course (graph may be disconnected)
for (let i = 0; i < numCourses; i++) {
if (!dfs(i)) return false;
}
return true;
}5
DFS vs BFS — When to Use Which
| Item | DFS — Use For | BFS — Use For |
|---|---|---|
| Path finding | Finding ANY path between two nodes (not necessarily shortest) | Shortest path in unweighted graphs |
| Tree traversal | Pre/In/Post-order — when you need parent before children or reverse | Level-order — when you need all nodes at depth d before depth d+1 |
| Backtracking | ✅ Natural fit — recursion with undo (pop) after each branch | ❌ Not suitable for backtracking |
| Topological sort | ✅ Post-order DFS naturally produces reverse topological order | ✅ Also possible with Kahn's algorithm (BFS-based) |
| Cycle detection | ✅ 3-color DFS detects back edges (cycles) efficiently | ✅ Also works but DFS is simpler for directed graphs |
| Memory | O(depth) — good for deep, narrow structures | O(width) — good for shallow, wide structures |
Backtracking is DFS with explicit undo
Backtracking problems (N-Queens, Sudoku solver, permutations, combination sum) are DFS with a specific pattern: add element to current path → recurse → remove element (backtrack). The "pop" after recursion is what makes it backtracking. Master this pattern for a huge class of interview problems.