Be the first user to complete this post

Add to List 
Binary TreePostorder Traversal  Non Recursive Approach
Objective: Given a binary tree, write a nonrecursive or iterative algorithm for postorder traversal.
Example:
Earlier we have seen "What is postorder traversal and recursive algorithm for it", In this article, we will solve it in an iterative/Non Recursive manner.
Approach:
 We have seen how we do inorder and preorder traversals without recursion using Stack, But postorder traversal will be different and slightly more complex than the other two. The reason is post order is nontail recursive ( The statements execute after the recursive call).
 If you just observe here, postorder traversal is just the reverse of preorder traversal (1 3 7 6 2 5 4 if we traverse the right node first and then the left node.)
 So the idea is to follow the same technique as preorder traversal and instead of printing it push it to another Stack so that they will come out in reverse order (LIFO).
 At the end just pop all the items from the second Stack and print it.
Pseudo Code:
 Push root into Stack_One.
 while(Stack_One is not empty)
 Pop the node from Stack_One and push it into Stack_Two.
 Push the left and right child nodes of the popped node into Stack_One.
 End Loop
 Popout all the nodes from Stack_Two and print it.
See the animated image below and code for more understanding.
Code:
Output:
4 5 2 6 7 3 1 4 5 2 6 7 3 1
Also Read: