In iterative depth-first traversal with an explicit stack, why push children in reverse order?

## The claim being tested The common belief is that an explicit stack simply *is* recursion, so swapping one for the other changes nothing observable. It changes two things: the order siblings are visited, and what the pending state can express. Both fall out of the same fact — a stack returns the most recently pushed item. ## Why recursion visits siblings in order Walk a nested outline: a document node with sections, each section with subsections. Recursive preorder visits the node, then recurses into child 1 and does not come back until that entire subtree is finished, then child 2, and so on. At any instant exactly **one** child is in flight; the others have not been touched yet. The order the loop iterates them is the order they are visited, with no reversal anywhere. ## Why the naive iterative version flips them The iterative form pops a node, visits it, and pushes all of its children at once. Now several siblings are pending simultaneously, sitting in one stack, and the next pop returns whichever was pushed **last**. Push children 1, 2, 3 in order and the traversal descends into child 3 first. The subtree order within each child is still depth-first, but siblings come out mirrored, and the mirroring compounds at every level. So you push right to left. Child 3, then 2, then 1 leaves child 1 on top, and the traversal descends into it first — identical to recursion. This is not a hack; it is compensating for the one place the two schemes differ. A fair question is whether it matters. If the traversal only needs to *reach* every node — summing sizes, collecting identifiers into a set — sibling order is irrelevant and you should push in whatever order is cheapest. It matters as soon as the output is ordered: rendering an outline, emitting a document in reading order, producing a deterministic diff, or writing a test that asserts a fixed visit sequence. Non-determinism in traversal order is a real source of flaky snapshot tests. ## Nodes versus frames The deeper difference is what each scheme stores. A recursive call keeps a frame per pending call: the node, the loop position among its children, and a **resume point** — the place execution continues once the child returns. That resume point is what makes post-order work possible for free: any statement written after the recursive call runs when the subtree completes. An explicit stack of bare nodes has no resume point. Once you pop a node and push its children, there is no record that you still owe it a closing action. That is why an iterative post-order traversal needs something extra, and the two standard answers are: - push a pair of (node, state) and re-push it with state advanced, so a node is seen once on the way down and once on the way up; or - keep a second stack, collecting nodes in a reversed order and unwinding it at the end. When an interviewer asks you to emit closing markers as well as opening ones — closing an outline level, emitting a closing tag, aggregating child results into a parent — this is the mechanic being probed. Answering it with a plain node stack is the standard miss. ## Space is not the same either At depth d with branching factor b, recursion keeps about **d** frames: one per ancestor of the current node. The explicit stack keeps every unvisited sibling along that whole path, on the order of **b*d** entries. For a wide, shallow structure the difference is large, and it is one reason a traversal that pushes eagerly can hold far more memory than the recursion it replaced. Pushing lazily — keeping an iterator position rather than all children — brings the profile back toward the recursive one at the cost of more bookkeeping. ## The one-line contrast worth knowing Swap the stack for a queue and the identical loop produces level-by-level order instead of depth-first. Nothing else in the code changes. That is the cleanest demonstration that the container's discipline, not the loop, chooses the traversal order — LIFO drives you deep, FIFO drives you wide. ## What a strong answer sounds like State the mechanism (LIFO hands back the last push, so pushing in order reverses siblings), state the fix (push right to left), then qualify it: order only matters when the output is ordered, the node stack cannot express post-visit work without an extra marker, and the peak memory profiles differ because recursion holds ancestors while the explicit stack holds pending siblings too.