Level order traversal in spiral form

Write a function to print spiral order traversal of a tree.
For below tree, function should print 1, 2, 3, 7, 6, 5, 4.

           [1]
          /   \
       [2]     [3]
      /  \     /  \ 
    [4]  [5] [6]  [7]



1) Recursive

For odd height , we print tree from Reverse ie,for node (1), (4,5,6,7) , ...
For Even height, we print tree from Front (2,3)
to do that in Level Order Traversal, we introduce variable flip and with that we can do that.

Algorithm

 printSpiral(tree){
   bool flip = false;
   for H = 1 to height(tree){
      printGivenLevel(root, H, flip);
      flip =!  flip
   }
}
printGivenLevel(root, height, flip){
if root is NULL then return;
if heightis 1, then
    print(root->data);
else if height greater than 1, then
    if(flip)
        printGivenLevel(root->left, height-1, flip);
        printGivenLevel(root->right, height-1, flip);
    else
        printGivenLevel(root->right, height-1, flip);

        printGivenLevel(root->left, height-1, flip);
}

 2) Iterative

Keep Two Stack S1, S2.
For Above example
Push 1 to S1.
Push 2,3 (R & L of 1) to S2.
Push 7,6 ( L & R of 3) to S1 and Push 5,4 (L & R of  2) to S1.
Continue this process

Algorithm

void printSpiral(struct node *root){
if root is NULL then return
stack<struct node*> S1

stack<struct node*> S2

 S1.push(root)

 While(S1 & S2 is not Empty){ //till both are not empty

   while(S1 not Empty){

   struct node *temp = S1.top()
  S1.pop()
  print temp->data
  //Push right and then left to S2//
  if(temp->right) S2.push(temp->right)
  if(temp->left) S2.push(temp->left) 

   }//while(s1 !Empty)

   while(S2 not Empty){

   struct node *temp = S2.top()
  S2.pop()
  print temp->data
  //Push left and then right to S1//
  if(temp->left) S1.push(temp->left)
  if(temp->right) S1.push(temp->right) 

   }//while(s2 !Empty)

   
}//While(S1,S2!Empty)


Labels: , , , , ,