What does the stack do during traversal without recursion?

AlgorithmsJunior~3 min read

Short answer

The stack in a non-recursive traversal replaces the system call stack: it holds state frames (a node and the context of processing it), provides LIFO returns to "return points," and lets you emulate pre/in/post processing of nodes and manage backtracking. This makes a depth-first traversal possible without recursion, with precise control over visit order.

Details

What the stack does in a non-recursive traversal

Emulates the call stack: each push is an "entry" into a subtask, each pop is a "return."
Holds return points and context: where we were, what's already processed, what's left (the processing phase, child index, iterator, and so on).
Provides LIFO order for backtracking: the last branch goes deeper than the first, which is exactly what a depth-first traversal (DFS) is.
Lets you implement different traversal orders (preorder/inorder/postorder) by controlling when a node is processed and the order in which neighbors/children are pushed.
Gives explicit control over memory and traversal order, avoiding the system stack's depth limit.

How it works step by step

Push the starting node (or state frame) onto the stack.
While the stack isn't empty: pop the top.
Process the node in the right phase (before/between/after children), depending on the traversal variant.
Push neighbors/children onto the stack in the order that makes the next pop yield the desired visit order (usually pushed in reverse display order).

What exactly goes onto the stack

A reference to the node (a vertex of the tree/graph).
The processing phase/state: enter/pre, mid/in, exit/post (often a boolean visited/expanded flag).
The current child's index, or a neighbor iterator (if children need to be processed one at a time).
Arbitrary context: a reference to the parent, an accumulated path/depth, intermediate computations.

Why a stack, not a queue

A stack (LIFO) gives a depth-first traversal and natural backtracking, an analog of recursion. A queue (FIFO) is needed for a breadth-first traversal (BFS), where it matters that all vertices of the current level are processed first.

Traversal orders and the stack's role

Preorder (node-left-right): we process the node right after popping it; then push the right child, then the left.
Inorder (left-node-right): the stack holds the path to the leftmost node; after popping we process the node and go into the right subtree.
Postorder (left-right-node): we use a flag/phase or two stacks; a node is processed only after its children.

Code examples (JavaScript)

1) DFS on a tree: preorder (node-left-right)

function preorderIter(root) {
  if (!root) return [];
  const res = [];
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    res.push(node.val);            // pre-processing
    if (node.right) stack.push(node.right); // push right first
    if (node.left) stack.push(node.left);   // so left comes off the stack sooner
  }
  return res;
}

// Node shape:
// { val: number, left: Node|null, right: Node|null }

2) DFS on a tree: inorder (left-node-right)

function inorderIter(root) {
  const res = [];
  const stack = [];
  let curr = root;
  while (curr || stack.length) {
    while (curr) {           // go down the left branches, remembering the path
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop();      // the left subtree is exhausted, process the node
    res.push(curr.val);
    curr = curr.right;       // then go into the right subtree
  }
  return res;
}

3) DFS on a tree: postorder (left-right-node) via a state flag

function postorderIter(root) {
  const res = [];
  if (!root) return res;
  const stack = [{ node: root, visited: false }];
  while (stack.length) {
    const { node, visited } = stack.pop();
    if (!node) continue;
    if (visited) {
      res.push(node.val); // post-processing
    } else {
      // Push a marker to revisit after the children
      stack.push({ node, visited: true });
      if (node.right) stack.push({ node: node.right, visited: false });
      if (node.left) stack.push({ node: node.left, visited: false });
    }
  }
  return res;
}

4) DFS on a graph (iterative, with a stack)

function dfsGraph(adj, start) {
  // adj: Map<Vertex, Vertex[]> or an object { v: [u1, u2, ...] }
  const visited = new Set();
  const stack = [start];
  const order = [];
  while (stack.length) {
    const v = stack.pop();
    if (visited.has(v)) continue; // important, to avoid cycles
    visited.add(v);
    order.push(v);
    const neighbors = (adj.get ? adj.get(v) : adj[v]) || [];
    for (let i = neighbors.length - 1; i >= 0; i--) {
      const u = neighbors[i];
      if (!visited.has(u)) stack.push(u);
    }
  }
  return order;
}

Generic "explicit stack of frames" template

function dfsIterGeneric(start) {
  // A frame holds the node and a phase: 'enter' (before children) or 'exit' (after children)
  const stack = [{ node: start, state: 'enter' }];
  while (stack.length) {
    const frame = stack.pop();
    const { node, state } = frame;
    if (!node) continue;
    if (state === 'enter') {
      // 1) pre-processing
      // ...
      // 2) Schedule post-processing
      stack.push({ node, state: 'exit' });
      // 3) Push children in reverse order, so the first logical child goes first
      const children = node.children || [];
      for (let i = children.length - 1; i >= 0; i--) {
        stack.push({ node: children[i], state: 'enter' });
      }
    } else {
      // post-processing
      // ...
    }
  }
}

Common errors

Missing a visited set for a graph, causing infinite loops.
The wrong push order, breaking the desired traversal order.
Ignoring the phase/visited flag for postorder, so a node gets processed too early.
Needlessly duplicating nodes on the stack, wasting memory and doing extra work.

Relation to recursion

Recursion automatically creates frames on the system stack: local variables, the return position, the phase. In the non-recursive approach, you explicitly create such frames and manage them by hand through your own stack, getting the same effect but with control over order and depth limits.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.