Recursive traversal of a deep rule tree overflows the call stack — what changes when you rewrite it with an explicit stack?

## What recursion was doing for you A recursive traversal keeps, for every node on the path from the root to the node being handled, one call frame recording where to resume — which child comes next, what local values to restore. That is a stack, and its depth is the tree's height. The frames live in a per-thread region that is fixed and small at creation, so a tree whose height is thousands or tens of thousands deep exhausts it. Note what the overflow implies: height, not size. A bushy tree of a billion nodes stands about thirty levels tall and will never come close; an overflow means the structure is degenerate — long chains of single-child nodes — or its depth is not bounded by anything you control. ## The rewrite An explicit stack stores the same pending work in ordinary allocated memory, which grows far beyond the call region. Preorder is the easy case, and it is the fragment interviewers ask you to produce at the whiteboard: ``` push(S, root) while not empty(S): node = pop(S) visit(node) if node.right != nil: push(S, node.right) if node.left != nil: push(S, node.left) ``` ## Why the push order reverses This is the detail the question is really testing. A stack is last-in-first-out: whatever went in most recently comes out first. Preorder requires the left subtree to be fully processed before the right one, so the left child must be the **next** thing popped, so it must be the **last** thing pushed. Push right, then left. Get it backwards and the walk is perfectly well-formed — it simply produces the mirrored order, node-right-left, which is a silent output bug rather than a crash, and one that a symmetric test tree will not catch. ## The other two orders are not mechanical **Inorder.** You cannot emit a node when you first meet it; its whole left subtree must come out first. The standard loop pushes nodes as it walks down the left spine, then pops one, emits it, and moves to that node's right child to repeat. So the loop has two phases rather than one. **Postorder.** The node must be emitted only after *both* children are finished, so a bare stack of nodes is not enough state — meeting a node on the stack no longer tells you which of the two situations you are in. The two standard fixes are to store a flag or a last-visited pointer alongside each entry, or to run a mirrored preorder (node, right, left) accumulating into a second stack and read that out in reverse. It is worth stating the reversal identity precisely: postorder equals the *mirrored* preorder reversed. "Postorder is preorder reversed" without the mirror step is simply false, and it is a common confident wrong answer. ## What the rewrite does and does not buy - **Time:** unchanged, O(n). - **Asymptotic space:** unchanged — still proportional to height, still linear on a degenerate tree. The rewrite does not make a deep walk cheap; it makes it survivable, because the memory comes from a region that grows rather than one with a hard early ceiling. - **Per-entry cost:** usually lower than a call frame, which carries saved registers and return addresses, but this is a constant-factor argument, not an asymptotic one. - **Readability:** worse, and that is a real cost. A three-line recursive walk is obviously correct; the iterative postorder with a last-visited pointer is code reviewers get wrong. ## The judgment call Before rewriting, ask what the height actually is and why. Options, roughly in order of how often they are right: 1. **Bound the depth in the data.** If a fraud-triage rule tree is 40,000 levels deep, the generator that produced it is the defect. Fixing the shape fixes the walk and everything else that touches the structure. 2. **Rewrite the one hot walk iteratively** and leave the shallow ones recursive. Mixed styles are fine when the reason is written down next to the loop. 3. **Rewrite all of them** for uniformity, accepting the readability cost, when depth is genuinely unbounded input — user-supplied or externally generated structures you cannot constrain. 4. **Raise the stack size** — available on most platforms, but it moves the cliff rather than removing it, and it is per-thread, so a fleet of workers pays the memory for every one. Also note what does *not* help: this recursion is not tail-recursive — a node's work continues after its children return — so no automatic tail-call transformation applies to postorder or inorder, and only the very last call of preorder would qualify. "The compiler will optimize it away" is a wrong answer here. ## Failure modes to name - Pushing left before right and shipping a mirrored order. - Pushing empty children and dereferencing them after the pop. - Claiming the iterative version is asymptotically cheaper in space. - Applying the plain preorder loop to postorder by moving the emit line. - Rewriting every walk in the codebase when only one meets deep input.