top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

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

+2 votes
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 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

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...