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

58 views

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

posted Jun 30, 2016

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;
}
``````
Similar Questions

Given a binary tree print it in inward spiral order i.e first print level 1, then level n, then level 2, then n-1 and so on.

For Ex -

``````         1
2           3
4    5       6     7
8 9  10 11  12 13  14 15
``````

Print- 1 15 14 13 12 11 10 9 8 2 3 7 6 5 4

Given binary tree is:

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

The output should be 1, 2, 3, 4, 5, 6, 7, 8

``````            1