Iterative Postorder Traversal (Two Stacks)
Do the postorder traversal (Left, Right, Root) of a binary tree without recursion, using two stacks. Return the node values as a list.
This is the iterative version of Binary Tree Postorder Traversal (LeetCode 145), solved the easy way. The one-stack version is the next topic.
Intuition
Every example below uses this tree:
1 12 / \3 2 34 / \ \5 4 5 6Look at postorder backwards. Postorder is Left, Right, Root, so its reverse is Root, Right, Left. That is just a preorder where the right child is explored before the left.
We already know how to do a preorder with a stack. So:
- Do a modified preorder (Root, Right, Left) and push each visited node onto a second stack.
- Popping the second stack reverses that order, giving Left, Right, Root, which is postorder.
Approach: Two Stacks
- If the tree is empty, return an empty list.
- Push the root onto
st1. - While
st1is not empty:- Pop a node from
st1and push it ontost2. - Push its left child onto
st1, then its right child. The right child is on top, so it is popped first.
- Pop a node from
- Pop everything from
st2into the answer. The order is postorder.
On the sample tree, st2 ends up (bottom to top) as 1, 3, 6, 2, 5, 4. Popping it gives 4, 5, 2, 6, 3, 1.
Code
class Solution {public:vector<int> postorderTraversal(TreeNode* root) {vector<int> ans;if (root == nullptr) return ans;stack<TreeNode*> st1, st2;st1.push(root);while (!st1.empty()) {TreeNode* node = st1.top();st1.pop();st2.push(node);if (node->left != nullptr) st1.push(node->left);if (node->right != nullptr) st1.push(node->right);}while (!st2.empty()) {ans.push_back(st2.top()->val);st2.pop();}return ans;}};
Complexity
Every node is pushed and popped once on each of the two stacks.
The second stack ends up holding every node, so extra space is O(n) regardless of tree shape. The one-stack solution improves this to O(h).