Print Spiral Order Traversal
Write a C Program to Print Spiral Order Traversal of a Binary Tree. Here’s simple Program to Print Spiral Order Traversal of a Binary Tree in C Programming Language.
Spiral Order Traversal
In spiral order traversal we need use two stacks. First stack is used to traverse the nodes at even level and second stack is used to traverse the nodes at odd level. Nodes at even level are stored in stack1 and are pushed in it from left to right order whereas nodes at odd level are stored in stack2 and are pushed in it from right to left order.
Also Read : : C Program for Level Order Traversal of binary tree using queue
Below is the source code for C Program to Print Spiral Order Traversal of a Binary Tree which is successfully compiled and run on Windows System to produce desired output as shown below :
SOURCE CODE : :
/* C Program to Print Spiral Order Traversal of a Binary Tree */
#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *lchild;
int info;
struct node *rchild;
};
struct node *insert(struct node *ptr, int ikey);
void display(struct node *ptr,int level);
int height(struct node *ptr);
void SpiralOrder(struct node* root);
void displayLevel_RtoL(struct node* root, int level);
void displayLevel_LtoR(struct node* root, int level);
int main()
{
struct node *root=NULL,*root1=NULL,*ptr;
int choice,k,item,level;
while(1)
{
printf("\n");
printf("1.Insert Tree \n");
printf("2.Display Tree \n");
printf("3.Traverse in Spiral Order\n");
printf("4.Quit\n");
printf("\nEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\nEnter the key to be inserted : ");
scanf("%d",&k);
root = insert(root, k);
break;
case 2:
printf("\n");
display(root,0);
printf("\n");
break;
case 3:
printf("\n");
SpiralOrder(root);
printf("\n");
break;
case 4:
exit(1);
default:
printf("\nWrong choice\n");
}/*End of switch */
}/*End of while */
return 0;
}/*End of main( )*/
struct node *insert(struct node *ptr, int ikey )
{
if(ptr==NULL)
{
ptr = (struct node *) malloc(sizeof(struct node));
ptr->info = ikey;
ptr->lchild = NULL;
ptr->rchild = NULL;
}
else if(ikey < ptr->info) /*Insertion in left subtree*/
ptr->lchild = insert(ptr->lchild, ikey);
else if(ikey > ptr->info) /*Insertion in right subtree */
ptr->rchild = insert(ptr->rchild, ikey);
else
printf("\nDuplicate key\n");
return(ptr);
}/*End of insert( )*/
void display(struct node *ptr,int level)
{
int i;
if(ptr == NULL )/*Base Case*/
return;
else
{
display(ptr->rchild, level+1);
printf("\n");
for (i=0; i<level; i++)
printf(" ");
printf("%d", ptr->info);
display(ptr->lchild, level+1);
}
}/*End of display()*/
/*Displays nodes on a level from left to right*/
void displayLevel_LtoR(struct node* ptr, int level)
{
if(ptr == NULL)
return;
if(level == 0)
printf("%d ", ptr->info);
displayLevel_LtoR(ptr->lchild, level-1);
displayLevel_LtoR(ptr->rchild, level-1);
}/*End of displayLevel_LtoR()*/
/*Displays nodes on a level from right to left*/
void displayLevel_RtoL(struct node* ptr, int level)
{
if(ptr == NULL)
return;
if(level == 0)
printf("%d ", ptr->info);
displayLevel_RtoL(ptr->rchild, level-1);
displayLevel_RtoL(ptr->lchild, level-1);
}/*End of displayLevel_RtoL()*/
void SpiralOrder(struct node* root)
{
int i,h = height(root);
for(i=0; i<height(root); i++)
if(i%2==0)
displayLevel_LtoR(root,i);
else
displayLevel_RtoL(root,i);
}/*End of SpiralOrder()*/
int height(struct node *ptr)
{
int h_left, h_right;
if (ptr == NULL) /*Base Case*/
return 0;
h_left = height(ptr->lchild);
h_right = height(ptr->rchild);
if (h_left > h_right)
return 1 + h_left;
else
return 1 + h_right;
}/*End of height()*/
OUTPUT : :
/* C Program to Print Spiral Order Traversal of a Binary Tree */
1.Insert Tree
2.Display Tree
3.Traverse in Spiral Order
4.Quit
Enter your choice : 1
Enter the key to be inserted : 6
1.Insert Tree
2.Display Tree
3.Traverse in Spiral Order
4.Quit
Enter your choice : 1
Enter the key to be inserted : 3
1.Insert Tree
2.Display Tree
3.Traverse in Spiral Order
4.Quit
Enter your choice : 1
Enter the key to be inserted : 4
1.Insert Tree
2.Display Tree
3.Traverse in Spiral Order
4.Quit
Enter your choice : 1
Enter the key to be inserted : 2
1.Insert Tree
2.Display Tree
3.Traverse in Spiral Order
4.Quit
Enter your choice : 1
Enter the key to be inserted : 1
1.Insert Tree
2.Display Tree
3.Traverse in Spiral Order
4.Quit
Enter your choice : 1
Enter the key to be inserted : 5
1.Insert Tree
2.Display Tree
3.Traverse in Spiral Order
4.Quit
Enter your choice : 1
Enter the key to be inserted : 7
1.Insert Tree
2.Display Tree
3.Traverse in Spiral Order
4.Quit
Enter your choice : 1
Enter the key to be inserted : 8
1.Insert Tree
2.Display Tree
3.Traverse in Spiral Order
4.Quit
Enter your choice : 2
8
7
6
5
4
3
2
1
1.Insert Tree
2.Display Tree
3.Traverse in Spiral Order
4.Quit
Enter your choice : 3
6 7 3 2 4 8 5 1
1.Insert Tree
2.Display Tree
3.Traverse in Spiral Order
4.Quit
Enter your choice : 4
Process returned 1
If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.
Thanks for reading the post…