Depth-First Search

Explanation

DFS starts at a source node, marks it as visited, and recursively explores each unvisited neighbor before moving to the next neighbor. The "depth-first" name captures the behavior: you plunge as deep as you can into one branch of the graph before exploring siblings. The call stack (or an explicit stack) remembers where to backtrack when a dead end is reached. On trees, DFS is simpler: no visited set needed because trees are acyclic (no path visits a node twice). The three DFS tree orderings are pre-order (process node, then children), in-order (left child, node, right child — for binary trees), and post-order (children, then node). In-order traversal of a BST produces sorted output; post-order is used for expression tree evaluation and safe deletion. On graphs, DFS requires a visited set to avoid infinite loops on cycles. DFS applications include: cycle detection (a back edge in DFS indicates a cycle), topological sort of a DAG (finish times in reverse order give topological order), finding connected components, detecting strongly connected components (Tarjan's/Kosaraju's algorithms), and solving maze/puzzle problems (explore one path to completion before trying another). DFS is typically implemented recursively (clean, matches the call stack to the algorithm's stack), but for deep graphs, this risks call stack overflow. The iterative version uses an explicit stack data structure.

Code Example

// DFS on a graph — iterative (avoids stack overflow)
function dfs(adj, start) {
  const visited = new Set();
  const stack = [start];
  const order = [];

  while (stack.length) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    order.push(node);

    // Push neighbors (reversed to maintain left-to-right order)
    for (const neighbor of [...(adj.get(node) || [])].reverse()) {
      if (!visited.has(neighbor)) stack.push(neighbor);
    }
  }
  return order;
}

// Recursive DFS — cleaner but limited by call stack depth
function dfsRecursive(adj, node, visited = new Set()) {
  visited.add(node);
  for (const neighbor of (adj.get(node) || [])) {
    if (!visited.has(neighbor)) dfsRecursive(adj, neighbor, visited);
  }
}

// Classic use: count islands on a 2D grid
function numIslands(grid) {
  let count = 0;
  const dfs = (r, c) => {
    if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length
        || grid[r][c] === '0') return;
    grid[r][c] = '0'; // mark visited
    [[-1,0],[1,0],[0,-1],[0,1]].forEach(([dr,dc]) => dfs(r+dr, c+dc));
  };
  for (let r = 0; r < grid.length; r++)
    for (let c = 0; c < grid[0].length; c++)
      if (grid[r][c] === '1') { dfs(r, c); count++; }
  return count;
}

Why It Matters for Engineers

DFS is fundamental to computer science and software engineering. Every time you walk a DOM tree, parse a JSON object recursively, resolve module dependencies, or run a file system traversal — you're doing DFS. Understanding DFS means understanding recursion, backtracking, and the call stack in a concrete, visual way. DFS problems are one of the most common interview topics. Number of Islands, the most-asked LeetCode problem historically, is a DFS/BFS problem on a grid. Course Schedule (topological sort), Clone Graph, Path Sum — all DFS patterns. Building pattern recognition for DFS problems is high-priority interview preparation.