Pre + Post + Inorder in One Traversal
Pre + Post + Inorder in One Traversal: produce preorder, inorder and postorder lists in a single traversal.
- 1 <= number of nodes <= 10⁵
- -10⁹ <= node value <= 10⁹
- All three orders must come from a single pass
Intuition
The all traversals in one problem asks for preorder, inorder and postorder lists produced by a single traversal instead of three separate ones.
The observation that makes it possible: during a depth-first walk, every node is passed through exactly three times, and each visit corresponds to one of the traversal orders:
- On arrival, before descending — that is preorder.
- Between finishing the left subtree and starting the right — that is inorder.
- After both subtrees are complete — that is postorder.
A recursive implementation makes this obvious: place three append statements at those three points in the function and all three lists build simultaneously.
Doing it iteratively is the interesting version, because the stack must remember which of the three visits a node is on. Push pairs of (node, state) where state runs 1 to 3. Popping a node records it in the list matching its state, then re-pushes it with the state incremented before pushing the next child.
The re-push is the mechanism. A node pushed back with state 2 sits underneath its left child on the stack, so it resurfaces only after that entire left subtree has been processed — which is precisely when inorder wants it. The same trick delivers state 3 after the right subtree finishes.
One stack carrying (node, state) pairs simulates the three points a recursive call passes through each node: before the left call, between the calls, and after the right call. Emitting at state 1, 2, 3 gives pre post inorder in one traversal — all three orders from a single pass — this is literally what the call stack does, made explicit.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(h) space.
See the three visits per node
A DFS touches each node on arrival, between its two subtrees, and on departure. Those three moments are exactly preorder, inorder and postorder, so one traversal can feed all three lists rather than repeating the walk.
Push (node, state) pairs
The stack holds a node together with a counter from 1 to 3 recording which visit is next. Without the state, a popped node gives no way to tell whether its subtrees have been handled.
State 1: record preorder, go left
Append the value to the preorder list, re-push the node with state 2, then push its left child. The node now sits beneath its left subtree and will not resurface until that subtree is finished.
State 2: record inorder, go right
Append to the inorder list, re-push with state 3, then push the right child. The re-push before the child push is what orders the stack correctly — reversing those two lines produces the wrong sequence.
State 3: record postorder and discard
Both subtrees are complete, so append to the postorder list and do not re-push. The node is finished and the stack moves on to whatever was beneath it.
Cost of the single pass
Each node is pushed and popped exactly three times, so the work is O(n) with a constant factor of three — still one pass rather than three separate O(n) traversals. Space is O(h) for the stack.
Solution & live demo
Common pitfalls
Not re-pushing the node with its next state
if state == 1:
pre.append(node.val)
if node.left: stack.append((node.left, 1))if state == 1:
pre.append(node.val)
stack.append((node, 2))
if node.left: stack.append((node.left, 1))The node must be revisited twice more, once after the left subtree and once after the right. Dropping the re-push means inorder and postorder never receive it.
Pushing the child before the node's next state
stack.append((node.left, 1)) stack.append((node, 2))
stack.append((node, 2)) if node.left: stack.append((node.left, 1))
A stack pops in reverse, so the child must be pushed last to be processed first. Reversing the order visits the node's state-2 step before its left subtree, scrambling the inorder output.
Running three separate traversals
return preorder(root), inorder(root), postorder(root)
stack = [(root, 1)]
Three passes is three times the tree walking, and the point of the exercise is seeing that all three orders are the same walk sampled at different moments. One pass makes that relationship visible.
Edge cases
Stack depth reaches n — same as recursion would.
All three lists empty.