top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

+2 votes
282 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 by Shubham Sharma

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+2 votes
 
Best answer

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;
}
answer Jun 30, 2016 by Shahsikant Dwivedi
Similar Questions
+3 votes

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

+6 votes

Given binary tree is:

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

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

+4 votes

Given binary tree is:

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

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

...