On this page
Description
Single-pass triple traversal produces preorder, inorder and postorder together, in one walk with an explicit stack. Each stack frame remembers which of its three visits the node is on. The first time it's on top, record preorder and go left. The second time, record inorder and go right. The third time, record postorder and pop. It's also the general recipe for turning any recursion into a loop: a frame that knows where it is.
We'll go from simple to more technical:
- The pattern: a stack of (node, phase) frames.
- Where getting several views in one walk helps.
- The bugs: state that doesn't stick, and updating the wrong frame.
- What it saves - and what it doesn't.
The approach
You could run three separate traversals. But in recursion, control comes back to each node exactly three times: before its left subtree, between its subtrees, and after them. Those three moments are exactly preorder, inorder and postorder. So keep each node on the stack with a counter of which visit it's on, and record the node in a different list each time.
| Top of the stack | Visit | Records | Then |
|---|---|---|---|
| 4 | 1st | preorder: 4 | push 2 |
| 2 | 1st | preorder: 2 | push 1 |
| 1 | 1st | preorder: 1 | no left child |
| 1 | 2nd | inorder: 1 | no right child |
| 1 | 3rd | postorder: 1 | pop |
| 2 | 2nd | inorder: 2 | no right child |
| 2 | 3rd | postorder: 2 | pop |
| 4 | 2nd | inorder: 4 | push 7 |
| 7 | 1st | preorder: 7 | no left child |
| 7 | 2nd | inorder: 7 | no right child |
| 7 | 3rd | postorder: 7 | pop |
| 4 | 3rd | postorder: 4 | pop |
The results are preorder 4 2 1 7, inorder 1 2 4 7 and postorder 1 2 7 4.
Java
Deque<Object[]> stack = new ArrayDeque<>(); // {TreeNode, Integer visitCount}
if (root != null) stack.push(new Object[]{root, 1});
while (!stack.isEmpty()) {
Object[] top = stack.peek();
TreeNode node = (TreeNode) top[0];
int count = (int) top[1];
if (count == 1) {
pre.add(node.val);
top[1] = 2;
if (node.left != null) stack.push(new Object[]{node.left, 1});
} else if (count == 2) {
in.add(node.val);
top[1] = 3;
if (node.right != null) stack.push(new Object[]{node.right, 1});
} else {
post.add(node.val);
stack.pop();
}
}
Python
stack = [[root, 1]] if root else [] # [node, visit_count] - a list, so the count changes in place
while stack:
top = stack[-1]
node, count = top
if count == 1:
pre.append(node.val)
top[1] = 2
if node.left:
stack.append([node.left, 1])
elif count == 2:
inorder.append(node.val)
top[1] = 3
if node.right:
stack.append([node.right, 1])
else:
post.append(node.val)
stack.pop()
A node's frame stays on the stack for all three visits; only its counter changes. It's popped after the third visit, once both children are done.
Where you'll see it
The bigger lesson is the frame itself. Any recursion can become a loop this way: each frame stores its own "where was I", and the loop resumes it from there. That's how you avoid stack overflows on very deep trees, and how tree iterators that yield one node at a time are built.
Which tool for which job?
| You need | Use |
|---|---|
| All three orders at once | one stack of (node, phase) frames |
| One order, iteratively | that order's own stack loop |
| Any recursion as a loop | frames that store their own "where was I" |
| A lazy in-order iterator | a stack of left spines (or a generator on shallow trees) |
| Recursion is fine (shallow trees) | just recurse - simplest |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Frames as Python tuples | the phase update is lost; it loops forever | lists, or a small mutable class |
Updating the phase through peek() after pushing a child | the child's phase changes; it loops | keep a reference to the parent's own frame |
| Pushing a null child | NullPointerException / None frames | push only real children |
| Popping in phase 2 | postorder is never recorded | pop only in phase 3 |
| Expecting a 3x speed-up | it's still 3 loop iterations per node | the saving is pushes and pops |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. A version reads the top frame into local variables, then pushes a new frame with the next count instead of updating the old one. What goes wrong?
Show answer
The old frame is still on the stack with its old count. When control comes back to it, the node is handled as if this were the earlier visit again, and the walk repeats work or loops. The technique needs the same frame, updated in place, to be found again later.
2. After pushing the left child, a version sets the parent's count with stack.peek()[1] = 2. What goes wrong?
Show answer
After the push, peek() returns the child's frame. So the child jumps to its second visit and never appears in preorder, while the parent stays on its first visit. When the child is popped, the parent pushes its left child again, forever. Update the parent through top, the reference you already hold.
3. Why does a node's frame stay on the stack for all three visits instead of being popped and pushed again?
Show answer
Popping would throw away the one fact the technique needs: which visit this is. One frame with a counter that changes in place answers "how many times have I been here" with no extra lookup.
Key takeaways
- Control returns to each node three times. Those three moments are preorder, inorder and postorder.
- Update a frame in place. A copy loses the visit count.
- After pushing a child, update the parent through your own reference to its frame, not through
peek(). - A node is popped only after its third visit.
- It's still O(n) with three loop steps per node. The saving is fewer pushes and pops, not two-thirds of the work.