How to print Spiral order travesal for a given Binary Tree?

Question

consider the tree:

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

spiral order traversal for the given tree is:1 2 3 7 6 5 4 or 1 3 2 4 5 6 7

Answer 1

spiralTravese function in the given programme takes up two stacks s1 and s2 and print even level from right to left and odd level from left to right,level of a binary tree starts with level 0. Time complexity is O(n).

#include<bits/stdc++.h>
using namespace std;

struct node{
    struct node *left;
    struct node *right;
    int data;
};
typedef struct node node;

node *newNode(int data){
    node *temp=(node*)malloc(sizeof(node));
    temp->left=temp->right=NULL;
    temp->data=data;
 return temp;
}
void spiralTraverse(node *root){
   stack <node *> s1,s2;
   s1.push(root);
   while(!s1.empty() || !s2.empty()){
     while(!s1.empty()){
        node *tmp=s1.top();
        s1.pop();
        printf("%d ",tmp->data);
        if(tmp->right)
          s2.push(tmp->right);
        if(tmp->left)
            s2.push(tmp->left);
     }
      while(!s2.empty()){
        node *tmp=s2.top();
        printf("%d ",tmp->data);
        s2.pop();
        if(tmp->left)
          s1.push(tmp->left);
        if(tmp->right)
            s1.push(tmp->right);
     }
   }
}
int main(){
  node *root=NULL;
  root=newNode(1);
  root->left=newNode(2);
  root->right=newNode(3);
  root->left->left=newNode(4);
  root->left->right=newNode(5);
  root->right->left=newNode(6);
  root->right->right=newNode(7);

  spiralTraverse(root);
  return 0;
}