Question: Find the post order traversal of a binary tree iteratively.
Answer: We have seen the recursive post order traversal of a Binary tree:
void postOrderTraversal(TreeNode *root)
{
if (!root) return;
postOrderTraversal(root->left);
postOrderTraversal(root->right);
cout << root->data;
}
So if we want to do the same thing iteratively; we just need to maintain 2 stacks child and parent. Follwoing is the algorithm of this method:
- Push the root node to the child stack.
- while child stack is not empty
- Pop a node from the child stack, and push it to the parent stack.
- Push its left child followed by its right child to the child stack.
- end while
- Now the parent stack would have all the nodes ready to be traversed in post-order. Pop off the nodes from the parent stack one by one and you will have the post order traversal of the tree.
Below is the C++ program for the same:
void postOrderTraversalIterativeTwoStacks(TreeNode *root)
{
if (!root) return;
stack<BinaryTree*> child;
stack<BinaryTree*> parent;
//Initialization
child.push(root);
while (!child.empty()) {
BinaryTree *curr = child.top();
parent.push(curr);
child.pop();
if (curr->left)
child.push(curr->left);
if (curr->right)
child.push(curr->right);
}
//Printing the post order traversal
while (!parent.empty()) {
cout << parent.top()->data << " ";
parent.pop();
}
}
Lets see a light example of how it works. Suppose we have a binary tree as shown at the right side and we need to compute its post order traversal. It's post order traversal will be
{A, C, E, D, B, H, I, G, F}
Let see step-step-step how two stacks grow and contract in each iteration:
| Child Stack | Parent Stack | |
| F | NIL | |
| G | ||
| B | F | |
| I | G | |
| B | F | |
| I | ||
| H | G | |
| B | F | |
| H | ||
| I | ||
| G | ||
| B | F | |
| B | ||
| H | ||
| I | ||
| D | G | |
| A | F | |
| D | ||
| B | ||
| H | ||
| E | I | |
| C | G | |
| A | F | |
| E | ||
| D | ||
| B | ||
| H | ||
| I | ||
| C | G | |
| A | F | |
| C | ||
| E | ||
| D | ||
| B | ||
| H | ||
| I | ||
| G | ||
| A | F | |
| A | ||
| C | ||
| E | ||
| D | ||
| B | ||
| H | ||
| I | ||
| G | ||
| NIL | F | |
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Akash, Its a wow!!! solution...
Thanks a ton Sree!
The best postOrder tree traversal algo on the web!!
Thanks so much!
Please publish iterative in-order traversal also.
@Anonymous: thanks, here you can find post for iterative in-order-traversal.
It's surely the cleanest approach I have ever seen. But the defect of this algorithm is the Parent stack has to grow to the number of node in the tree. I think there is an algorithm that could make parent stack only being the depth of the tree?
¡¡¡Muchas GRacias!!! =D
Esta genial!!! ^^
one of the neatest codes for iterative postorder traversal i could find on web..thanx for the post
I have few comments on the approach. Surely it will print the post order. The worst case requirements of stack is O(n), where as at any point of time we need not to store the leaf nodes, nodes with only left subtree which is already explored.
Can we optimize the solution using only one stack?
I am thinking on the lines of the approach based on parent pointer. We will encounter two scenarios,
1. Crawling down the tree
2. Crawling up the tree
Again in case 2, it can be from left child or from right child. If we climb from left child, we further process right subtree (if one presents). If we climb from right subtree, we process the current node, and move one step up.
Here is my code with parent pointer.
void PostOrder(BinaryTree *pRoot) {
BinaryTree *prev = NULL;
BinaryTree *curr = pRoot;
BinaryTree *dang;
while( curr ) {
dang = curr;
// Going down the tree
if( !prev || prev->lChild == curr || prev->rChild == curr ) {
if( curr->lChild )
curr = curr->lChild;
else if( curr->rChild )
curr = curr->rChild;
else {
printf("%4d", curr->key);
curr = curr->parent;
}
} else if( prev == curr->lChild ) {
// Climbing up from left
if( curr->rChild )
curr = curr->rChild;
else {
printf("%4d", curr->key);
curr = curr->parent;
}
} else {
// Climbing up from right
printf("%4d", curr->key);
curr = curr->parent;
}
prev = dang;
}
}
I guess the above approach can be explored with one stack, and without parent pointer.
Awesome Solution.
Below is just a thought.In no manner is it better than your code.I am just suggesting a possible re-factoring and code reuse here.
If you reverse the post order traversal you will see that all it does is to print the current node and then print the right child whenever available.When it runs out of right children it shifts to the left child and starts printing them.
This means we can use the code we use for printing the pre-order of a tree,replace all left references by right references and instead of printing push them into another stack.
Then when you break just print the second stack.
//C++ implementation,prints reverse
void stack_postorder(struct tree_node* root)
{
static stack S;
printf("\n");
while(1)
{ while(root)
{
S.push(root);
printf("%d ",root->data);
root= root->right;
}
if(S.size()==0)
return;
root = S.top();
S.pop();
root = root->left;
}
}
//above code prints the reverse of //the post order of a tree
A Diff Version
void paccess()
{
struct node *a[100];
int ind=-1;
struct node *temp=start;
while(temp!=NULL || index != -1)
{
if(temp!=NULL)
{
arr[++index] = temp;
a[++ind] = temp;
temp=temp->right;
}
else {
temp=arr[index--];
temp=temp->left; }
}
while(ind!=-1)
printf("%d ",a[ind--]->info);
}