How to implement tree traversal without recursion? What data structure can help?

Tree traversal without recursion can be implemented using a stack — a classic data structure for simulating recursive calls.

For example, depth-first search (DFS) — preorder, inorder, or postorder — uses a stack to store nodes that need to be visited.

An example of preorder traversal of a tree without recursion in JavaScript:

function preorderTraversal(root) {
  if (!root) return;
  const stack = [root];
  while (stack.length > 0) {
    const node = stack.pop();
    console.log(node.value); // process node
    if (node.right) stack.push(node.right); // push right first so left is processed first
    if (node.left) stack.push(node.left);
  }
}

Breadth-first search (BFS) uses a queue instead of a stack.

Thus, a stack is a key data structure for tree traversal without recursion, allowing to save traversal state and node visit order.