In an explicit-stack rewrite of a recursive tree walk, why do children come out reversed?

## The two schedules are not the same A recursive stock counter over a product catalogue loops over a category's children and calls itself on each one. The schedule is: descend fully into child 0 and return, then descend fully into child 1, and so on. At any instant the live frames are exactly the path from the root to the node being processed. The explicit-stack rewrite has a different schedule. It pops a node, does that node's work, and pushes **all** of its children at once. Because a stack returns the most recently pushed item, the last child pushed is the next one popped — the group is consumed in reverse. ``` stack = empty push(stack, root) total = 0 while stack is not empty: node = pop(stack) total = total + node.stock for i in 0..length(node.children)-1: push(stack, node.children[i]) return total ``` This code is not broken. It is a correct depth-first walk that touches every node exactly once — it just walks siblings right to left, which is not what the recursion it replaced did. ## Why the bug hides If all you compute is a total, order is irrelevant: addition gives the same answer whatever sequence you visit in, so the rewrite passes every test that checks the number. The reversal only becomes visible when the traversal's *order* is part of the contract: - **First match wins** — "find the first category with zero stock" now returns a different category. - **Emitted sequence** — a report, an export, or a stream of records changes order, and something downstream that assumed catalogue order breaks. - **Tie-breaking** — two categories with equal stock, and the reported winner flips. - **Bounded work** — "scan until you have collected 50 items" collects a different 50. - **Snapshot comparison** — golden-file tests start failing for reasons nobody can explain. This is the classic bug in the whole "convert this recursion to an explicit stack" exercise, and interviewers ask about it precisely because the naive rewrite looks obviously equivalent. ## The fix, and its cost Push the children from the highest index down to the lowest: ``` for i in length(node.children)-1 downto 0: push(stack, node.children[i]) ``` Now the leftmost child is on top and pops first, matching the recursion. It is one line, but it is a line that reads backwards from the intent it implements, which is why it deserves a comment and a test. Alternatively, hand the frontier a different discipline: consuming the frontier oldest-first instead of newest-first preserves sibling order but abandons depth-first behaviour entirely and explores level by level, which is a different traversal with different peak-memory characteristics — not a drop-in replacement for a recursion you were trying to preserve. ## The other thing that changed: peak memory The recursion holds one frame per level of the current path — depth-many frames. The stack rewrite holds every unexplored sibling along that path: up to roughly the branching factor times the depth of entries. For a wide catalogue that is a materially larger count. It is usually still the better deal, for two reasons. Each entry is a node reference, not a full frame with parameters, locals and a return address, so the per-item cost is far smaller. And the structure lives in memory that grows on demand rather than in the fixed-size region reserved for a thread's call stack, so "too deep" stops being a hard crash and becomes ordinary memory pressure you can observe. But if you claim the rewrite "uses less memory", be ready to say which memory: fewer bytes, in a place with a much more forgiving limit, but more live entries. ## Reviewing one of these Three questions catch nearly every defect in a hand-rolled stack walk. Does the pop order reproduce the recursion's visit order, or was it silently reversed? Is any node pushed more than once, or pushed before its predecessor's work is recorded? And does a test exist that distinguishes the orders — a fixture whose siblings are individually identifiable, asserting the sequence of visits rather than an order-independent sum? A test that only checks the total is a test that would pass on the reversed version.