Iterative Postorder Traversal (One Stack)
Do the postorder traversal (Left, Right, Root) of a binary tree without recursion, using only one stack. Return the node values as a list.
This is the harder follow-up to the two-stack version and a frequent interview question, because postorder is the one traversal where a node must be visited after returning from both children.
Intuition
Every example below uses this tree:
1 12 / \3 2 34 / \ \5 4 5 6With one stack we walk down-left pushing nodes, like inorder. But when we reach a stack top we cannot just record it: we may have come back from its left child (so the right subtree is still pending) or from its right child (so we are really done with it).
The trick is to peek at the top without popping and look at its right child:
- If the right child exists and is not yet processed, go there.
- If there is no right child, the node is ready to record.
- After recording a node, every ancestor whose right child is the node we just recorded is also finished, so we record those too before moving on.
Approach: Peek the Top and Check the Right Child
Keep node (starting at the root) and a stack.
- While
nodeis not null, push it and go left. - Otherwise peek the top and set
right = top.right.- If
rightis not null, setnode = rightand continue from step 1 to explore the right subtree. - If
rightis null, pop the top aslastand add its value. Then, while the stack is not empty and the new top's right child islast, pop that node too, updatelast, and add its value.
- If
- Stop when
nodeis null and the stack is empty.
The inner while loop is what handles a subtree finishing: when we finish a right child, its parent is finished immediately, and so on up the chain.
Code
class Solution {public:vector<int> postorderTraversal(TreeNode* root) {vector<int> ans;stack<TreeNode*> st;TreeNode* node = root;while (node != nullptr || !st.empty()) {if (node != nullptr) {st.push(node);node = node->left;} else {TreeNode* right = st.top()->right;if (right != nullptr) {node = right;} else {TreeNode* last = st.top();st.pop();ans.push_back(last->val);while (!st.empty() && st.top()->right == last) {last = st.top();st.pop();ans.push_back(last->val);}}}}return ans;}};
Complexity
Each node is pushed once and popped once. The inner while loop pops nodes that are already counted, so it adds no extra passes.
Only one stack is used and it holds a single root-to-node path, so O(h). This is the improvement over the two-stack version.