· By John Kavanagh

Choosing DFS, BFS, or an Explicit Stack in TypeScript

An aerial view of a person at a junction of paths through green woodland.
Image by Hiboy, licensed from Unsplash.

"Use a traversal" is a fairly incomplete instruction. Sometimes we need the fewest edges to a destination. Sometimes we need to finish every child before processing its parent. Sometimes we only need to know what is reachable, but the input can be deep enough to exhaust the JavaScript call stack.

I choose between BFS, recursive DFS, and an explicit stack by the information the next step needs. Breadth‑first search preserves distance layers. Depth‑first search preserves a current branch. An explicit stack lets us decide exactly which parts of a suspended depth‑first call to retain.

Those are operational differences, not competing tastes in syntax. Replacing recursion with pop doesn't automatically preserve recursive traversal order, and replacing a queue with a stack doesn't preserve shortest‑path distances. The data structure changes what can be concluded when a node is first encountered.


Fix the Graph Assumptions First

The examples use adjacency lists indexed by integer node numbers. Every neighbour is a valid index, the starting node exists, and the graph may contain cycles. The lists can describe directed or undirected edges; for an undirected graph, the caller supplies both directions.

Each traversal starts from one node, so disconnected components remain unvisited. To traverse the entire graph, an outer loop must start a new search from each still‑unvisited node. That is a different interface from returning only the component reachable from one source.

I retain the adjacency‑list order deliberately. When several neighbours are possible, this order determines which one a depth‑first traversal visits first. Distances in an unweighted graph don't depend on that tie order, but a traversal transcript or chosen parent tree can.


BFS When the Number of Edges Matters

BFS processes nodes in increasing distance from the start. A queue preserves discovery order: all nodes at distance one are processed before distance two, and so on. For edges with equal cost, the first discovery of a node gives its shortest distance in number of edges.

type Graph = readonly (readonly number[])[];

const shortestDistances = (graph: Graph, start: number): number[] => {
  const distances = Array<number>(graph.length).fill(-1);
  const queue = [start];
  distances[start] = 0;
  for (let head = 0; head < queue.length; head++) {
    const node = queue[head];
    for (const next of graph[node]) {
      if (distances[next] !== -1) continue;
      distances[next] = distances[node] + 1;
      queue.push(next);
    }
  }
  return distances;
};

The distance array doubles as a visited marker. We set the distance before appending a node, so two already queued parents cannot enqueue the same neighbour repeatedly. Marking only when removing from the queue would allow duplicate pending work.

A head index avoids removing the first array element on every iteration. The loop reads queue[head] and advances the index, leaving earlier slots in place. This is simple and avoids relying on repeated front‑removal costs.

There is a memory detail worth stating accurately: this array retains all discovered node numbers until the function returns. Its backing storage is O(V), even when the currently active frontier is narrow. Describing its memory as only the current layer width would be wrong for this implementation. A reusable compacting queue could release old entries, but the distance result would still occupy O(V).


DFS When following a Branch is Useful

Recursive DFS visits one neighbour's reachable descendants before moving to the next neighbour. The call stack records where each parent should resume after its child returns. That makes it a natural expression of nested work.

const depthFirstOrder = (graph: Graph, start: number): number[] => {
  const seen = new Set<number>();
  const order: number[] = [];
  const visit = (node: number): void => {
    if (seen.has(node)) return;
    seen.add(node);
    order.push(node);
    for (const next of graph[node]) visit(next);
  };
  visit(start);
  return order;
};

Marking a node before visiting its neighbours prevents cycles from recursing forever. Without that step, even a two‑node undirected edge would bounce between its endpoints. The returned order records entry into each node, not completion of its descendants.

Consider adjacency lists [[1, 2], [3], [3], []]. Recursive DFS from zero enters nodes in the order zero, one, three, two. BFS discovers them as zero, one, two, three. Both reach the same set, but only BFS's discovery layers justify the shortest unweighted distances.

Recursive code also consumes call‑stack space proportional to the active depth. A long chain can be a problem even when the total graph is modest. MDN documents excessive recursion errors, but there is no single portable safe recursion depth I would build an input contract around. Engine limits and the work done in each call matter.


An Explicit Stack Can Preserve the Return Point

For simple reachability, a stack of node numbers is often enough. If we need the same entry order as recursive DFS, or work after all children finish, we must retain more context. The frame below stores the current node and the index of its next neighbour to inspect.

type VisitEvent = { node: number; phase: 'enter' | 'exit' };
type VisitFrame = { node: number; nextChild: number };

const depthFirstEvents = (graph: Graph, start: number): VisitEvent[] => {
  const seen = new Set<number>([start]);
  const events: VisitEvent[] = [{ node: start, phase: 'enter' }];
  const frames: VisitFrame[] = [{ node: start, nextChild: 0 }];
  while (frames.length > 0) {
    const frame = frames[frames.length - 1];
    if (frame.nextChild === graph[frame.node].length) {
      events.push({ node: frame.node, phase: 'exit' });
      frames.pop();
      continue;
    }
    const next = graph[frame.node][frame.nextChild++];
    if (seen.has(next)) continue;
    seen.add(next);
    events.push({ node: next, phase: 'enter' });
    frames.push({ node: next, nextChild: 0 });
  }
  return events;
};

At the top of the loop, the final frame is the currently active call. If it has another neighbour, we advance its neighbour index before descending. When the child finishes, the parent frame is still present with the correct resume position.

If the frame has exhausted its neighbours, we emit an exit event and remove it. That mirrors returning from a recursive call. The separate event phase makes completion visible rather than trying to infer it from a node appearing somewhere in a flat array.

For our four‑node example, the events are: enter zero, enter one, enter three, exit three, exit one, enter two, exit two, exit zero. When two inspects its edge to three, three is already seen, so it does not receive another pair of events. Exit means this traversal has finished processing that node's adjacency list, not that every possible incoming route has been explored separately.


Why Pushing All Neighbours Can Change the Order

A common iterative translation pushes every neighbour at once. Because a stack removes the final item first, pushing in forward order reverses which sibling is explored first. Reversing the push order fixes that simple tree case, but graphs introduce another wrinkle when nodes are marked seen at push time.

One sibling may mark a shared descendant before the other sibling's branch reaches it. The resulting parent relationships and entry order can differ from recursive DFS even if the set of reached nodes is correct. For reachability, that is often acceptable. For an exact traversal transcript, it is not.

Frames avoid the ambiguity by selecting one next neighbour at a time, just as the recursive loop does. I would pay for that extra field when return‑time work or exact order matters, and use a simpler node stack when the output only promises reachability. The required behaviour should decide how much state we preserve.


Complexity Depends on What We Retain

With V reachable nodes and E outgoing edges inspected from them, each algorithm performs O(V + E) traversal work under the usual constant‑time visited‑set model. Cycles don't multiply the node visits because discovery happens once, though every listed edge still needs inspection. The BFS distance‑array initialisation also touches every supplied graph node, so its total time is O(graph.length + E), including disconnected nodes.

Recursive DFS uses O(depth) active call frames, plus its visited set and output. The explicit‑frame version uses O(depth) active frames too, but stores them in ordinary heap‑allocated arrays rather than the language call stack. Its events array retains two events per visited node, so total auxiliary storage is O(V).

BFS retains distances for every graph node in this implementation, including unreachable ones, and its head‑index queue retains every discovered node. Its total space is therefore O(graph size), not just the largest frontier. Returning an event stream through a callback could avoid retaining the event output, but would change how errors and partial processing are exposed to the caller.


Tests That Distinguish the Promises

I test a single node, a chain, a cycle, disconnected nodes, and a diamond with a shared descendant. For BFS, an independent repeated‑edge relaxation reference checks distances. For explicit DFS, a small recursive event reference checks both enter and exit order, not merely the final visited set.

A deep‑chain test belongs only to the iterative implementations when its purpose is to demonstrate avoiding call‑stack growth. Deliberately running an enormous recursive chain until it crashes doesn't establish a useful portable limit. The iterative algorithm still needs memory; it has changed where the suspended work lives.

My circular queue article explores queue storage directly. My Network Delay Time walkthrough shows why unequal edge costs need a priority queue instead of ordinary BFS, and my stop‑limited flights article explains when node identity alone is insufficient state. For these unweighted traversals, I would first decide what discovery or completion must mean, then choose the container that preserves it.


Have a complex web platform issue?

Tell me what is blocked, what has changed, and what needs to be true after the fix. I'll come back with a practical next step.