PROGRAMMING INTERVIEWS

Answer: We usually use a queue for level order traversal of a queue. If we want to use the same here, how will we change direction of traversal on every alternate level?

If we think logically then we will see that we need stack in place of queue. Now again a single stack won’t serve our purpose here, we need 2 stacks: stack1 for right to left and stack2 for left to right. For identifying, whether we need to put data in stack1 or stack2, we need a flag (left2right) to indicate direction (after a level finishes).

Initially, left2right is true and we push root node in stack1 and that’s our beginning point. Now since after root node, first level fished, we toggle left2right. Until stack1 is empty, we pop values from stack1 and push values based on left2right flag. Once stack1 finishes, we toggle left2right again and switch stack’s role.

For clarification, when left2right is true, push left node first in stack and then right node. Similarly left2right is false, push right node first in stack and then left node.

Code:

void ZigZagLevelOrder(tree *root) {
 stack<tree*> stack1, stack2, *cur_level, *next_level, *temp;
 bool left2right = true;

 cur_level = &stack1;
 next_level = &stack2;

 // push root in stack
 cur_level->push(root); 
 while (!cur_level->empty()) {
   tree *node = cur_level->top();
   cur_level->pop();
   if (node) {
     cout << node->data << " ";
     if (left2right) {
       next_level->push(node->left);
       next_level->push(node->right);
     } else {
       next_level->push(node->right);
       next_level->push(node->left);
     }
   }
   if (cur_level->empty()) {
     left2right = !left2right;
     // swap stacks
     temp = Cur_level;
     cur_level = next_level;
     next_level = temp;     
   }
 }
}