All Three in One
The Unified Walk
In Lesson 1 we said something important: all three traversals perform the same walk through the tree. Every node is visited three times — on the way down, after the left subtree returns, and after the right subtree returns. Preorder, inorder, and postorder just capture different moments of that walk.
This lesson makes that idea concrete. You'll write a single iterative loop that produces all three traversals simultaneously — one walk, three outputs.
The (Node, State) Technique
Instead of pushing bare node pointers onto the stack, push a pair: (node, state). The state is an integer — 0, 1, or 2 — that tracks where you are in this node's lifecycle.
- state = 0: You just arrived at this node. This is the preorder moment. Process it for preorder, increment state, push the node back, then push the left child.
- state = 1: You've returned from the left subtree. This is the inorder moment. Process it for inorder, increment state, push the node back, then push the right child.
- state = 2: You've returned from both subtrees. This is the postorder moment. Process it for postorder. Done with this node — don't push it back.
Each node gets pushed onto the stack up to three times. Each time it's popped, it's in a different state.
The Tree
The Code
void allThreeTraversals(Node* root,
vector<int>& preorderResult,
vector<int>& inorderResult,
vector<int>& postorderResult) {
if (!root) return;
stack<pair<Node*, int>> nodeStack;
nodeStack.push({root, 0});
while (!nodeStack.empty()) {
auto [current, state] = nodeStack.top();
nodeStack.pop();
if (state == 0) {
preorderResult.push_back(current->value);
nodeStack.push({current, 1});
if (current->left) nodeStack.push({current->left, 0});
} else if (state == 1) {
inorderResult.push_back(current->value);
nodeStack.push({current, 2});
if (current->right) nodeStack.push({current->right, 0});
} else {
postorderResult.push_back(current->value);
}
}
}
Read the state == 0 block carefully. You process the node for preorder, then push it back with state 1 (so it'll be there when you come back), then push the left child with state 0 (it needs the full treatment). The left child is on top of the stack, so it gets processed next — exactly like a recursive call.
When the left child (and all its descendants) are done, the stack unwinds back to this node with state 1. Now the inorder block runs: process for inorder, push back with state 2, push the right child.
When the right child is done, the stack unwinds back with state 2. Process for postorder. Don't push back. This node is finished.
Full Trace
This is the trace that makes it click. Follow every push and pop.
| Step | Pop (node, state) | Action | Push to Stack | Stack After (top→bottom) | Pre | In | Post |
|---|---|---|---|---|---|---|---|
| 0 | — | Init | (1,0) | [(1,0)] | [] | [] | [] |
| 1 | (1,0) | Pre:1, push back, push left | (1,1), (2,0) | [(2,0), (1,1)] | [1] | [] | [] |
| 2 | (2,0) | Pre:2, push back, push left | (2,1), (4,0) | [(4,0), (2,1), (1,1)] | [1,2] | [] | [] |
| 3 | (4,0) | Pre:4, push back, no left | (4,1) | [(4,1), (2,1), (1,1)] | [1,2,4] | [] | [] |
| 4 | (4,1) | In:4, push back, no right | (4,2) | [(4,2), (2,1), (1,1)] | [1,2,4] | [4] | [] |
| 5 | (4,2) | Post:4 | — | [(2,1), (1,1)] | [1,2,4] | [4] | [4] |
| 6 | (2,1) | In:2, push back, push right | (2,2), (5,0) | [(5,0), (2,2), (1,1)] | [1,2,4] | [4,2] | [4] |
| 7 | (5,0) | Pre:5, push back, no left | (5,1) | [(5,1), (2,2), (1,1)] | [1,2,4,5] | [4,2] | [4] |
| 8 | (5,1) | In:5, push back, no right | (5,2) | [(5,2), (2,2), (1,1)] | [1,2,4,5] | [4,2,5] | [4] |
| 9 | (5,2) | Post:5 | — | [(2,2), (1,1)] | [1,2,4,5] | [4,2,5] | [4,5] |
| 10 | (2,2) | Post:2 | — | [(1,1)] | [1,2,4,5] | [4,2,5] | [4,5,2] |
| 11 | (1,1) | In:1, push back, push right | (1,2), (3,0) | [(3,0), (1,2)] | [1,2,4,5] | [4,2,5,1] | [4,5,2] |
| 12 | (3,0) | Pre:3, push back, push left | (3,1), (6,0) | [(6,0), (3,1), (1,2)] | [1,2,4,5,3] | [4,2,5,1] | [4,5,2] |
| 13 | (6,0) | Pre:6, push back, no left | (6,1) | [(6,1), (3,1), (1,2)] | [1,2,4,5,3,6] | [4,2,5,1] | [4,5,2] |
| 14 | (6,1) | In:6, push back, no right | (6,2) | [(6,2), (3,1), (1,2)] | [1,2,4,5,3,6] | [4,2,5,1,6] | [4,5,2] |
| 15 | (6,2) | Post:6 | — | [(3,1), (1,2)] | [1,2,4,5,3,6] | [4,2,5,1,6] | [4,5,2,6] |
| 16 | (3,1) | In:3, push back, push right | (3,2), (7,0) | [(7,0), (3,2), (1,2)] | [1,2,4,5,3,6] | [4,2,5,1,6,3] | [4,5,2,6] |
| 17 | (7,0) | Pre:7, push back, no left | (7,1) | [(7,1), (3,2), (1,2)] | [1,2,4,5,3,6,7] | [4,2,5,1,6,3] | [4,5,2,6] |
| 18 | (7,1) | In:7, push back, no right | (7,2) | [(7,2), (3,2), (1,2)] | [1,2,4,5,3,6,7] | [4,2,5,1,6,3,7] | [4,5,2,6] |
| 19 | (7,2) | Post:7 | — | [(3,2), (1,2)] | [1,2,4,5,3,6,7] | [4,2,5,1,6,3,7] | [4,5,2,6,7] |
| 20 | (3,2) | Post:3 | — | [(1,2)] | [1,2,4,5,3,6,7] | [4,2,5,1,6,3,7] | [4,5,2,6,7,3] |
| 21 | (1,2) | Post:1 | — | [] | [1,2,4,5,3,6,7] | [4,2,5,1,6,3,7] | [4,5,2,6,7,3,1] |
Final results:
- Preorder: [1, 2, 4, 5, 3, 6, 7]
- Inorder: [4, 2, 5, 1, 6, 3, 7]
- Postorder: [4, 5, 2, 6, 7, 3, 1]
All match Lesson 1. One walk, three outputs.
Why This Matters
This technique isn't just a clever trick. It reveals something fundamental:
Preorder, inorder, and postorder are not three different algorithms. They are three observations of the same depth-first walk. The (node, state) technique makes this explicit — state 0 is preorder, state 1 is inorder, state 2 is postorder.
This has practical consequences:
-
If you need just one traversal, you can simplify by only using the relevant state. The iterative preorder from Lesson 2 is the state-0-only version. The iterative inorder is the state-0-and-1 version.
-
If you need to interleave processing — say, compute something top-down (preorder) and then aggregate bottom-up (postorder) — this framework does it in a single pass. Push state-0 for the top-down work, and the same node at state-2 does the bottom-up work.
-
It generalizes to \(n\)-ary trees. For a node with \(k\) children, you'd use states \(0\) through \(k\). State \(i\) means "I've finished processing the first \(i\) children." State \(k\) is the postorder moment.
Complexity
- Time: \(O(n)\). Each node is pushed and popped exactly 3 times. Total operations: \(3n\).
- Space: \(O(h)\) where \(h\) is the height of the tree. The stack never holds more than \(3h\) entries (at most 3 entries per node on the current path from root to the deepest point).
This is the same complexity as the individual iterative traversals. You're not paying extra for getting all three — you're just making the unified walk explicit.
Getting Just One Traversal
If you only need postorder (the hardest one iteratively), strip out the preorder and inorder lines:
vector<int> iterativePostorder(Node* root) {
vector<int> result;
if (!root) return result;
stack<pair<Node*, int>> nodeStack;
nodeStack.push({root, 0});
while (!nodeStack.empty()) {
auto [current, state] = nodeStack.top();
nodeStack.pop();
if (state == 0) {
nodeStack.push({current, 1});
if (current->left) nodeStack.push({current->left, 0});
} else if (state == 1) {
nodeStack.push({current, 2});
if (current->right) nodeStack.push({current->right, 0});
} else {
result.push_back(current->value);
}
}
return result;
}
This is arguably cleaner than the lastVisited one-stack method from Lesson 2 — the state variable makes the logic transparent. You always know exactly where you are in the node's lifecycle.
Try It
The starter code has an allThreeTraversals function with a TODO. Fill it in and verify:
Predict before running: How many total push operations happen for the 7-node tree? Each node is pushed 3 times (states 0, 1, 2). Leaf nodes still get pushed 3 times — they just don't push any children. Total: \(3 \times 7 = 21\) pushes.
Challenge: Extend this to an \(n\)-ary tree. Each node has a vector<Node*> children. State \(i\) means "push child \(i\) next." The postorder moment is when state equals children.size().
Challenge 2: Use the (node, state) framework to compute the diameter of a binary tree in a single iterative pass. At state 0, do nothing (going down). At state 2, you have the heights of both subtrees — compute the path through this node and update a global max.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| LC 144 — Binary Tree Preorder Traversal | leetcode.com/problems/binary-tree-preorder-traversal | Easy |
| LC 94 — Binary Tree Inorder Traversal | leetcode.com/problems/binary-tree-inorder-traversal | Easy |
| LC 145 — Binary Tree Postorder Traversal | leetcode.com/problems/binary-tree-postorder-traversal | Easy |
| LC 589 — N-ary Tree Preorder Traversal | leetcode.com/problems/n-ary-tree-preorder-traversal | Easy |
| LC 590 — N-ary Tree Postorder Traversal | leetcode.com/problems/n-ary-tree-postorder-traversal | Easy |