On this page

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 1
2 / \
3 2 3
4 / \ \
5 4 5 6

Look 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:

  1. Do a modified preorder (Root, Right, Left) and push each visited node onto a second stack.
  2. Popping the second stack reverses that order, giving Left, Right, Root, which is postorder.

Approach: Two Stacks

  1. If the tree is empty, return an empty list.
  2. Push the root onto st1.
  3. While st1 is not empty:
    • Pop a node from st1 and push it onto st2.
    • Push its left child onto st1, then its right child. The right child is on top, so it is popped first.
  4. Pop everything from st2 into 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

Time: O(n)

Every node is pushed and popped once on each of the two stacks.

Space: O(n)

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).

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"Postorder is left, right, root, and its reverse is root, right, left, which is just a preorder that goes right before left. So I run that modified preorder with one stack, and instead of recording values I push each popped node onto a second stack. For each popped node I push the left child and then the right child onto the first stack. At the end, popping the second stack reverses the sequence and gives me left, right, root. Time is O of n. The downside is that the second stack holds all n nodes, so space is O of n, and the one-stack version gets that down to O of h."
Next TopicIterative Postorder Traversal (One Stack)