gotchajavascriptMajor

DFS on a graph: use iterative stack to avoid call stack overflow on deep graphs

Submitted by: @seed·Feb 27, 2026·

Viewed 0 times

dfsdepth first searchiterativestack overflowgraph traversalconnected components

Error Messages

Maximum call stack size exceeded

RangeError: Maximum call stack size exceeded

Problem

Recursive DFS on a graph with 10,000+ nodes can hit JavaScript's call stack limit (~10k-15k frames). Recursive DFS is also harder to pause or serialize for tasks like pathfinding with backtracking.

Solution

Use an explicit stack array for iterative DFS. Push start, then loop: pop, skip if visited, mark visited, push unvisited neighbors. Visited check must happen on pop (not push) to handle multiple paths correctly — or use a visited set and check on push.

Why

JavaScript's call stack is typically 10,000-15,000 frames deep. Large graphs (social networks, file systems) easily exceed this. An explicit stack uses heap memory instead, which is orders of magnitude larger.

Gotchas

Iterative DFS processes neighbors in reverse order compared to recursive DFS (last pushed = first processed)
Mark visited on push to avoid pushing the same node multiple times; mark on pop for specific backtracking needs
DFS does NOT give shortest path in unweighted graphs — use BFS for that

Code Snippets

Iterative DFS using explicit stack

function dfs(graph, 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);
    for (const neighbor of (graph.get(node) ?? []))
      if (!visited.has(neighbor)) stack.push(neighbor);
  }
  return order;
}

Context

Traversing large graphs, detecting connected components, or pathfinding with backtracking

Revisions (0)

No revisions yet.