Inorder Tree Traversal without Recursion

C++:
01 void inorderTravel(Node* head)
02 {
03     stack <Node*> S;
04     S.push(head);
05     Node* prv=head;
06     while(!S.empty()){
07         Node* tmp=S.top();
08         S.pop();
09         if((prv==head)||(prv->left==tmp)||(prv->right==tmp)){
10             if(tmp->right)
11                 S.push(tmp->right);
12             S.push(tmp);
13             if(tmp->left)
14                 S.push(tmp->left);
15             prv=tmp;
16             continue;
17         }
18         cout<<tmp->value<<” “;
19         prv=tmp;
20     }
21 }
Advertisements
This entry was posted in 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