Tree Traversal: Order and State

Move the action, not the whole algorithm

The sorted-order claim requires a valid binary search tree; inorder on an arbitrary binary tree does not sort it. A DOM has an ordered list of children rather than binary left/right links, so preorder, postorder, and level order generalize directly, while this binary inorder template does not.

function traversalOrders(root) {
  const preorder = [], inorder = [], postorder = [];
  function visit(node) {
    if (!node) return;
    preorder.push(node.val);
    visit(node.left);
    inorder.push(node.val);
    visit(node.right);
    postorder.push(node.val);
  }
  visit(root);
  return { preorder, inorder, postorder };
}

1. On [5,2,8], enter 5: record it for preorder, then pause its frame while visiting 2.
2. Node 2 records its preorder, inorder, and postorder actions; its two missing-child calls immediately return.
3. Resume 5: record its inorder action, then pause again while visiting 8.
4. After 8 finishes, resume 5 and record its postorder action. The parent frame survives while either child runs.

Inherited state versus returned state

• Depth and ancestor constraints flow downward. For BST validation, pass a lower and upper bound; checking only immediate children misses ancestor violations.
• Height and subtree answers flow upward. A missing child has a neutral contribution defined by the problem, not one universal value.
• A level-order traversal keeps a queue and records its current end before processing a level. Children appended afterward belong to the next level.
• Avoid shared mutable path arrays without push/pop restoration or deliberate copying. Sibling branches must not inherit each other's work.

An explicit stack for deep binary trees

When recursion depth is unsafe, collect root-right-left order with a stack and reverse it into left-right-root. This returns node objects, so a later bottom-up computation can associate child results with the exact nodes rather than their potentially repeated values.

function postorderNodes(root) {
  if (!root) return [];
  const order = [];
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    order.push(node);
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }
  return order.reverse();
}

1. On [5,2,8], pop 5 and push left 2, then right 8.
2. The stack pops 8 before 2, giving the collected order [5,8,2].
3. Reverse it to [2,8,5]. Both children now precede their parent.

• This template assumes a proper acyclic binary tree with no shared children.
• It stores the entire order, using O(N) auxiliary space. It is not an O(H)-space frame-based traversal.
• An explicit stack avoids recursive calls; it does not remove the memory needed to track traversal work.

Height and width are different costs

• Visiting N nodes once takes O(N) time.
• Recursive DFS uses O(H) call-stack space, excluding collected outputs. H can be N on a chain, not always log N.
• BFS can hold a whole frontier: O(W) auxiliary queue space with a queue that releases processed entries, where W is maximum width. A head-index array retaining every visited node instead uses O(N) storage.
• The traversalOrders example intentionally returns three N-element arrays, so its total auxiliary/output storage is O(N) even though recursion alone uses O(H).
• JavaScript runtimes have finite call stacks. An algorithm can be linear-time and still overflow on a sufficiently deep input.

Mistakes and Counterexamples