Binary tree post-order traversal iterative.

Given a binary tree, you need to print the elements in post-order iteratively without using recursion.

C++:
01 void print_postorder(Node *head)
02 {
03     stack <Node *> tree_stack;
04     Node *prev;
05     tree_stack.push(head);
06     while(!tree_stack.empty()){
07         Node* tmp=tree_stack.top();
08         tree_stack.pop();
09         if((tmp->left==prev)||(tmp->right==prev)){
10             cout<<tmp->value<<” “;
11             prev=tmp;
12             continue;
13         }
14         if((tmp->left)||(tmp->right))
15             tree_stack.push(tmp);
16         else
17             cout<<tmp->value<<” “;
18         if(tmp->right)
19             tree_stack.push(tmp->right);
20         if(tmp->left)
21             tree_stack.push(tmp->left);
22         prev=tmp;
23     }
24 }
Advertisements
This entry was posted in Stack and Queue, Tree. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s