Binary Tree Post-Order Traversal Iterative Solution
October 27, 2010 in binary tree
Given a binary tree, print the elements in post-order iteratively without using recursion.
We know the elements can be printed post-order easily using recursion, as follow:
1 2 3 4 5 6 | void postOrderTraversal(BinaryTree *p) { if (!p) return; postOrderTraversal(p->left); postOrderTraversal(p->right); cout << p->data; } |
This is the most difficult of all types of iterative tree traversals. You should attempt this problem: Binary Search Tree In-Order Traversal Iterative Solution before this as it is an easier problem. The easiest of all iterative tree traversals is Pre-Order Traversal.
Post-order traversal is useful in some types of tree operations:
- Tree deletion. In order to free up allocated memory of all nodes in a tree, the nodes must be deleted in the order where the current node can only be deleted when both of its left and right subtrees are deleted.
- Evaluating post-fix notation.
If you keep visited flags in the binary tree while traversing, the problem could be solved in a more direct manner. But we will not discuss this solution here, as it has already been discussed in Wikipedia’s article on Tree Traversal. Here, we discuss a solution without using any visited flags, which seems challenging to solve.
Hint:
As usual, a stack-based solution is necessary when there is no parent pointer available in the tree. Try to follow the post-order traversal of a sample binary tree. When should you print a node’s value? Note under what condition it traverses up/down the tree. Try to use a variable to store the previously-traversed node. How would it help when it traverses up/down the tree?
Solution:
We use a prev variable to keep track of the previously-traversed node. Let’s assume curr is the current node that’s on top of the stack. When prev is curr‘s parent, we are traversing down the tree. In this case, we try to traverse to curr‘s left child if available (ie, push left child to the stack). If it is not available, we look at curr‘s right child. If both left and right child do not exist (ie, curr is a leaf node), we print curr‘s value and pop it off the stack.
If prev is curr‘s left child, we are traversing up the tree from the left. We look at curr‘s right child. If it is available, then traverse down the right child (ie, push right child to the stack), otherwise print curr‘s value and pop it off the stack.
If prev is curr‘s right child, we are traversing up the tree from the right. In this case, we print curr‘s value and pop it off the stack.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | void postOrderTraversalIterative(BinaryTree *root) { if (!root) return; stack<BinaryTree*> s; s.push(root); BinaryTree *prev = NULL; while (!s.empty()) { BinaryTree *curr = s.top(); // we are traversing down the tree if (!prev || prev->left == curr || prev->right == curr) { if (curr->left) { s.push(curr->left); } else if (curr->right) { s.push(curr->right); } else { cout << curr->data << " "; s.pop(); } } // we are traversing up the tree from the left else if (curr->left == prev) { if (curr->right) { s.push(curr->right); } else { cout << curr->data << " "; s.pop(); } } // we are traversing up the tree from the right else if (curr->right == prev) { cout << curr->data << " "; s.pop(); } prev = curr; // record previously traversed node } } |
The above method is easy to follow, but has some redundant code. We could refactor out the redundant code, and now it appears to be more concise. Note how the code section for printing curr‘s value get refactored into one single else block. Don’t worry about in an iteration where its value won’t get printed, as it is guaranteed to enter the else section in the next iteration.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | void postOrderTraversalIterative(BinaryTree *root) { if (!root) return; stack<BinaryTree*> s; s.push(root); BinaryTree *prev = NULL; while (!s.empty()) { BinaryTree *curr = s.top(); if (!prev || prev->left == curr || prev->right == curr) { if (curr->left) s.push(curr->left); else if (curr->right) s.push(curr->right); } else if (curr->left == prev) { if (curr->right) s.push(curr->right); } else { cout << curr->data << " "; s.pop(); } prev = curr; } } |
Alternative Solution:
An alternative solution is to use two stacks. Try to work it out on a piece of paper. I think it is quite magical and beautiful. You will think that it works magically, but in fact it is doing a reversed pre-order traversal. That is, the order of traversal is a node, then its right child followed by its left child. This yields post-order traversal in reversed order. Using a second stack, we could reverse it back to the correct order.
Here is how it works:
- Push the root node to the first stack.
- Pop a node from the first stack, and push it to the second stack.
- Then push its left child followed by its right child to the first stack.
- Repeat step 2) and 3) until the first stack is empty.
- Once done, the second stack would have all the nodes ready to be traversed in post-order. Pop off the nodes from the second stack one by one and you’re done.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | void postOrderTraversalIterativeTwoStacks(BinaryTree *root) { if (!root) return; stack<BinaryTree*> s; stack<BinaryTree*> output; s.push(root); while (!s.empty()) { BinaryTree *curr = s.top(); output.push(curr); s.pop(); if (curr->left) s.push(curr->left); if (curr->right) s.push(curr->right); } while (!output.empty()) { cout << output.top()->data << " "; output.pop(); } } |
Complexity Analysis:
The two-stack solution takes up more space compared to the first solution using one stack. In fact, the first solution has a space complexity of O(h), where h is the maximum height of the tree. The two-stack solution however, has a space complexity of O(n), where n is the total number of nodes.
Anonymous said on October 27, 2010
nice post.
So, what is the time complexity of these 3 methods?
daniel008 said on August 19, 2012
struct Node
{
int m_value;
Node* m_left;
Node* m_right;
};
tyepdef std::pair Data;
void PostTraverse(Node* d)
{
stack s;
if (d) s.push(Data(d, true));
while (!s.empty())
{
Data t = s.pop();
if (t.second)
{
s.push(Data(t.first, false;))
if (t.first->m_right)
s.push(Data(t.first->m_right, true));
if (t.first->m_left)
s.push(Data(t.first->m_left, true));
}
else
{
std::cout <m_value;
}
}
}
1337c0d3r said on October 27, 2010
All of them runs in O(N) time complexity, where N is the total number of nodes.
Abhishek Jain said on November 15, 2010
Another way of doing PostOrder Iterative traversal using two stacks
Here I have taken other childStack to store right child of each node.
public class PostOrderItr2
{
static StackLL stack;
static StackLL childStack;
public static void postOrderTrav(Node node)
{
stack = new StackLL();
childStack = new StackLL();
if(node == null)
{
return;
}
while(true)
{
if(node != null)
{
stack.push(node);
if(node.right != null)
{
childStack.push(node.right);
}
node = node.left;
}
else if(!stack.isEmpty())
{
Node parent = stack.peek();
if(!childStack.isEmpty() && parent.right == childStack.peek())
{
node = childStack.pop();
}
else
{
stack.pop();
System.out.print(" " + parent.data);
}
}
else
{
return;
}
}
}
}
Guohua said on November 18, 2010
Great idea of using two stacks, it is very easy to understand and implement, thank you
Tracy said on January 26, 2011
@1337c0d3r:
I'm quite sure that my code of using one stack for post-order traversal works. You can use the same example above to go through it. I made iterative in-order, pre-order and post-order traversal as similar as possible:
void postorderNoR(const Node *root)
{
stack s;
const Node *itr = root;
while (itr || !s.empty()) {
if (!itr) {
while (!s.empty() &&
itr == s.top()->right) {
itr = s.top();
s.pop();
printf("%d ",itr->value);
}
itr = s.empty() ? NULL : s.top()->right;
}
else
{
s.push(itr);
itr = itr->left;
}
}
}
// *********************
void inorderNoR(const Node *root)
{
stack s;
const Node *itr = root;
while (itr || !s.empty()){
if (!itr){
itr = s.top();
s.pop();
printf("%d ",itr->value);
itr = itr->right;
}
else{
s.push(itr);
itr = itr->left;
}
}
}
// *********************
void preorderNoR(const Node *root)
{
stack s;
const Node *itr = root;
while (itr || !s.empty()){
if (!itr){
itr = s.top();
s.pop();
itr = itr->right;
}
else{
printf("%d ",itr->value);
s.push(itr);
itr = itr->left;
}
}
}
Tracy said on January 26, 2011
@1337c0d3r:
Er… How to post the source code as the way you did in the main post?
1337c0d3r said on January 26, 2011
@Tracy:
There's no easy way to do this now in Blogger (Blogger will automatically discard some symbols in the comment). Could you paste your code here?
http://ideone.com/
Tracy said on January 26, 2011
@1337c0d3r:
I just posted them here:
https://ideone.com/g17bt
1337c0d3r said on January 26, 2011
@Tracy:
Cool! Thanks for sharing, I'll look into it soon
arnimarj said on February 13, 2011
A python solution which stores a state with each stack entry, showing which of two children to push next
def post_order_b_(root):
….if root == None:
……..return
….stack = [[root, 0]]
….while len(stack) > 0:
……..node, state = stack[-1]
……..if state == 2:
…………visit(node)
…………stack.pop()
……..else:
…………child = (node.GetLeft() if state == 0 else node.GetRight())
…………stack[-1][1] += 1
…………if child != None:
…………….stack.append([child, 0])
gt said on March 14, 2011
There is something called MORRIS inorder traversal which does not require any stack usage to perform the traversal… it uses a tree-transformation technique to get the traversal done iteratively … not sure if we could tweak it for post or pre-order traversal … i vaguely recollect it is not possible for some reason … although i am not sure myself …
why cant we try and come up with an approach that doesnt involve usage of stack per se ? … because if we do, we are merely mimicking the recursive approach….
codingC said on June 2, 2011
@1337c0d3r:
Thank you for the excellent solution. The two stack solution is indeed brilliant. But it seems to me not a reversed pre-order traversal as what you mentioned.
amal said on June 4, 2011
hi, can you help me to solve this question plese:
write a c-program to arrange the inputted data item on root and other items on left or right nodes of the binary tree. that program should also provide to display the following functions:
1.in order traversal
2.pre order traversal
3.post order traversal
4.exit
anonymous said on June 5, 2011
Hey loser, why ask help for your home works here? Get out of here!
Bala said on June 25, 2011
@1337c0d3r:
Thank you so much for the post; the explanation articulates your solution in a very neat manner.
Nathan said on June 29, 2011
I guess an easy way to do this is that, every time you push a node to the stack, push it twice. The first one is used to simulate the function call, the second is to simulate the function frame:
Nathan said on June 29, 2011
sorry, formated code:
Kshitij said on July 11, 2011
I went through your iterative inorder traversal page and tried to write the post order one and I guess i have got a bit simpler code than the one mentioned here. See if you can edit the post to include this for other users:
public void postOrder_iterative(Tree root){
Stack s = new Stack();
Tree current = root;
Tree prevElement = null;
while(!s.empty() || current !=null){
if(current !=null){
s.push(current);
current = current.left;
}else{
current = s.lastElement();
if(current.right == null || current.right == prevElement){
System.out.println(current.value);
prevElement = current;
s.pop();
current = null;
}else{
current = current.right;
}
}
}
}
Kshitij said on July 11, 2011
Karthick said on July 12, 2011
Well, can the preorder traversal be done this way. I tried a few cases and it seemed to be alright.
This way, it seems like we have to push only the right child of every node.
Is this correct?
tryingout said on August 5, 2011
Another solution which uses extra space than first solution mentioned above but does it using single stack http://tryingout101.blogspot.com/2011/08/iterative-postorder-of-binary-tree-part.html
Ankur said on September 26, 2011
For method 2 , complxity shud be O(n) ..how is it O(h) or O(logn) ..please explain …
prasad said on March 3, 2012
Hi, i came up with this solution. With my initial testing it seems working fine. Can you please take a look at it. Thanks.
void postorder(node* root)
{
if(!root) return;
stack s;
bool FirstTime = true;
node* r = root;
node *q, *last_q;
last_q = null;
while(!s.IsEmpty() || FirstTime)
{
FirstTime = false;
while(r != null)
{
s.push(r);
r = r->left;
}
q = s.pop();
if(q->right == NULL || q->right == last_q)
{
print(q->data);
last_q = q;
}
else
{
s.push(q);
r = r->right;
}
}
}
harelg said on May 7, 2012
another solution:
you can always kinda cheat your way around with pushing a dummy node right after you push yourself down the stack.
every node except a leaf would be pushed once by its parent and once by itself (after pushing right then left children then dummy)
and when you pop a dummy you pop another one and print
stv said on July 3, 2012
The 3rd way is brilliant. Thanks for good explanation. I guess the order to push the left/right child nodes to the tree for the first stack should be swapped, so that when we print, we print left-right-root instead of right-left-root.
et said on July 26, 2012
For the two stack solution. I think this step is reversed.
3) Then push its left child followed by its right child to the first stack.
It should be push it right child followed by its left child.
SG said on August 12, 2012
pseudo code:
Stack s=new Stack();
s.push(root);
do
{
if(root->left !=NULL && root->left->visited==false)
{
stack.push(root->left);
root=stack.top;
continue;
}
if(root->right!=NULL && root->right->visited==false)
{
stack.push(root->right);
root=stack.top;
continue;
}
stack.peek().visited=true;
display(stack.top);
stack.pop();
root=stack.peek();
}while(stack.peek()!=empty)
I just push in the root first into the stack. Along with the key value at each node I also maintain a visited flag to not get caught up into a loop wherein I am traversing the same node again and again. As soon as both the if conditions I have mentioned become invalid, I pop off the node from the stack, ultimately achieveing post order traversal.
Please leave your valuable feedback. I think this works, but if there are any mistakes please point me to them..
Rocky said on October 30, 2012
Nice blog!
Frankie said on November 19, 2012
Can the below code work?
void PostOrder(TreeNode* pRoot)
{
if(pRoot == NULL)
return;
TreeNode* pNode = pRoot;
TreeNode* pPrev = NULL; // latest visited node
stack st;
while(pNode != NULL || !st.empty())
{
while(pNode != NULL)
{
st.push(pNode);
pNode = pNode -> left;
}
pNode = st.top();
// node has no right child or right child has just been visited
if(pNode -> right == NULL || pNode -> right == pPrev)
{
visit(pNode);
st.pop();
pPrev = pNode;
pNode = NULL;
}
else
{
pNode = pNode -> right;
}
}
}
zyfo2 said on February 4, 2013
we can change the iterative inorder traversal a little bit to work for postorder
public static ArrayList inorderTraversal(TreeNode root) {
ArrayList l=new ArrayList();
Stack s=new Stack();
TreeNode current=root;
boolean child=false;
while(!s.isEmpty()||current!=null){
if(current!=null){
s.push(current);
current=current.left;
child=false;
}
else{
current=s.peek();
if(!child){current=current.right;child=true;}
else{current=s.pop(); l.add(current.val);
if(!s.isEmpty()&¤t==s.peek().left){child=false;}
else if(!s.isEmpty()&¤t==s.peek().right){child=true;}
current=null;
}
}
}
return l;
}
Kislay Verma said on March 2, 2013
The second solution is absolutely brilliant!!!
aaaaaaamie said on March 25, 2013
The two stack solution is awesome.
I’ve got a short working version in Java:
while(!stack.isEmpty()) {
TreeNode cur = stack.peek();
if(cur == null) stack.pop();
// not popping this one yet
else if(cur.right != prev) {
if(cur.left == prev)
stack.push(cur.right);
else
stack.push(cur.left);
}
else {
output.add(stack.pop().val);
}
prev = cur;
}