• The number of nodes is in the range [0, 10⁵]
• -100 <= Node.val <= 100
• No recursion — the traversal must be driven by an explicit stack and a loop
• The tree may be a single chain, so the height can equal the node count

The recursive traversal from the previous problem is correct and short, and in an interview it is usually what you should write first. It has exactly one weakness, and it is not about speed. When a function calls itself, the runtime saves a stack frame — which node this call is on, and which line it had reached — and it can only stack up so many of those. The limit is typically a few thousand frames. On a bushy tree that is irrelevant, because the frames alive at any moment equal the current depth and a balanced tree of a million nodes is only about 20 deep. But a tree is allowed to be a single chain of children, and then depth equals node count. Ten thousand nodes in a chain, ten thousand live frames, and the program dies with a stack overflow before printing anything.

The fix is not to invent a new traversal. It is to notice what the call stack was storing and store it ourselves, in ordinary memory, which is enormous by comparison. So the real question is: what information was the machine keeping for us, and what is the least we can get away with keeping?

Pre-order records a node the instant it arrives, so by the time we leave a node we owe nothing to it — only to its children. That means the pending work is just a set of subtrees still to be walked, and we can keep those subtree roots in a list. The order in which we take them off decides the traversal, so it must be: the left child before the right child, and both before anything owed to an ancestor.

A stack gives exactly that. A stack is a list where you add and remove at the same end, so the most recently added item comes out first — last in, first out. If, after recording a node, we push its right child and then its left child, the left child sits on top and is taken next, while the right child waits underneath, above everything older. That is precisely "left subtree fully, then right subtree, then back to whatever the ancestors were owed."

if not root: return []
stack, out = [root], []
while stack:
    node = stack.pop()
    out.append(node.val)          # record on arrival — pre-order
    if node.right: stack.append(node.right)   # pushed FIRST, so taken LAST
    if node.left:  stack.append(node.left)    # pushed second, so taken next

Try the same trick for in-order and it falls apart immediately. In-order says a node is written only after its entire left subtree, so when we first reach a node we are not allowed to do anything with it yet — but we also cannot forget it, because we will need it later, after the left side finishes. A node therefore has two distinct encounters: the arrival, when we merely remember it, and the return, when we finally write it. The stack has to hold the "remembered but not yet written" nodes.

That gives the shape: from wherever we stand, walk down the left links as far as they go, pushing every node passed. When the left link runs out, the node on top of the stack has no unvisited left subtree left, so it is the smallest thing outstanding — pop it and write it. Its left side is done and it is done, so all that remains of it is its right subtree; step into that child and repeat the same drill-down from there.

stack, out, curr = [], [], root
while curr or stack:
    while curr:                # drill down the left edge, remembering as we go
        stack.append(curr)
        curr = curr.left
    curr = stack.pop()         # nothing left of this node remains — write it
    out.append(curr.val)
    curr = curr.right          # only its right subtree is still owed

The loop condition needs both tests, and the reason is worth stating. curr being non-null means there is a subtree we have not entered; the stack being non-empty means there are remembered nodes we still owe a write to. The walk is finished only when both are exhausted — a stack that is momentarily empty while curr still points somewhere is a perfectly normal mid-traversal state, which happens every time we pivot into a right subtree from the very last remembered node.

Post-order is the awkward one, because a node must wait for both children, so on returning to a node you have to know whether you are coming back from the left child or the right one — which normally means storing a flag per node, or a "last visited" pointer. There is a neater route.

Take the pre-order code and swap the two pushes, so the walk becomes node, then right subtree, then left subtree. Call that sequence M. By definition M(x) = [x] followed by M(right) followed by M(left). Now reverse the whole finished list. Reversing a concatenation reverses each part and flips their order, so reverse(M(x)) = reverse(M(left)), then reverse(M(right)), then [x]. That is exactly the definition of post-order — left, right, node — provided reversing works for the smaller subtrees, which the same argument gives us all the way down to the empty tree. So one push-swap plus one final reversal turns the easiest traversal into the hardest one.

stack, out = [root] if root else [], []
while stack:
    node = stack.pop()
    out.append(node.val)
    if node.left:  stack.append(node.left)    # swapped, so RIGHT is taken first
    if node.right: stack.append(node.right)
return out[::-1]                             # reverse: node,right,left → left,right,node

Time is still O(N): every node is pushed once and popped once, a constant amount of work each. Space is still O(H) — at any moment the stack holds a root-to-current path, same as the frames did. Nothing got asymptotically cheaper. What changed is where that memory lives: heap instead of the runtime's small fixed call stack, which is the difference between handling a 10⁵-node chain and crashing on it. Post-order's reversal trick does hold the full output list before flipping it, but the output is O(N) anyway, so that costs nothing extra.

The transferable idea is broader than trees: any recursion can be converted into a loop plus an explicit stack, because the call stack is just a stack you were not managing yourself. The work is only ever in deciding what a frame really needed to remember — for pre-order, nothing but the pending subtrees; for in-order, the ancestors owed a write; for post-order, additionally which side you are returning from, which is exactly why the reversal trick is worth knowing. You will use this conversion again outside trees, whenever depth might blow the stack. And if even O(H) memory is forbidden, there is one more level: Morris Traversal rewires the tree's own null links to remember the way back, reaching O(1) space.