Printing a binary tree in zig zag level-order

Given a binary tree, print out the tree in zig zag level order (ie, from left to right, then right to left for the next level and alternate between). Output a newline after the end of each level.

     3
   /  \
  9   20
     /  \
    15    7

For example, the zig zag level order output of the tree above is:

3
20 9
15 7
C++:
01 void PrintZigZag(Node* head)
02 {
03     if(head==NULL)
04          return;
05      stack <Node*> q1;
06      stack <Node*> q2;
07      stack <Node*>* q=&q1;
08      stack <Node*>* p=&q2;
09 
10      bool flag=true;
11      q1.push(head);
12      while(!q->empty()){
13          Node* tmp=q->top();
14          q->pop();
15          cout<<tmp->value<<” “;
16          if(flag){
17             if(tmp->left)
18                 p->push(tmp->left);
19             if(tmp->right)
20                 p->push(tmp->right);
21          }else{
22             if(tmp->right)
23                 p->push(tmp->right);
24             if(tmp->left)
25                 p->push(tmp->left);
26 
27          }
28          if(q->empty()){
29              flag=!flag;
30              cout<<endl;
31              stack <Node*>* t=q;
32              q=p;
33              p=t;
34          }
35      }
36 }
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