On this page

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

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

  1. While node is not null, push it and go left.
  2. Otherwise peek the top and set right = top.right.
    • If right is not null, set node = right and continue from step 1 to explore the right subtree.
    • If right is null, pop the top as last and add its value. Then, while the stack is not empty and the new top's right child is last, pop that node too, update last, and add its value.
  3. Stop when node is 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

Time: O(n)

Each node is pushed once and popped once. The inner while loop pops nodes that are already counted, so it adds no extra passes.

Space: O(h)

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.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"With one stack I go left pushing nodes. When the pointer is null I peek at the top instead of popping it, and look at its right child. If a right child exists, I go explore it. If there is no right child, the node is finished, so I pop it and record it. Then, because finishing a right child means its parent is finished too, I keep popping while the new top has the node I just recorded as its right child. That handles a whole subtree completing at once. Each node is pushed and popped once, so time is O of n, and the stack holds one path, so space is O of h."
Next TopicPreorder, Inorder & Postorder in One Traversal