Spiral Order Traversal of a Tree using Recursion

«
»

This is a C Program for Spiral Order Traversal of a Tree using Recursion.

Problem Description

In this program we are going to create a tree, and we will traverse it in a spiral order. Spiral Traversal basically means first traversing the nodes in a tree left to right then right to left or vice versa. If for a particular level, we are going left to right then the levels before and after that particular level should be traversed right to left if they exist.

Expected Input and Output

Case 1. A Balanced Tree having same weight on both sides of root node. For example:

 If the input tree is    
                    25
                  /    \
                 27     19
                / \     / \
              17  91   13  55
then here the expected spiral traversal will be 25  19  27  17  91  13  55

Case 2. An unbalanced tree having weight more on right side of root node. For example:

If the input tree is          
                   1
                /     \
               13      2
                        \
                         3
                          \
                           4
                            \
                             5
then the expected spiral traversal of tree in this case will be 1  2  13  3  4  5

Case 3. Tree having just one node. For example:

advertisement
advertisement
If the input tree is
                    15
then the expected spiral traversal of the tree here will be 15
Problem Solution

1. We will use level order traversal technique to do a spiral traversal of any given tree.
2. In level order we simply traverse all the nodes level by level from left to right (say in a function f1()). Here, we are additionally going to create a function (say function f2()) that traverses all the levels from right to left and we will call both theses functions alternatively using a flag or the value of iterator.

Participate in Data Structure I Certification Contest of the Month Now!
Program/Source Code

Here is source code of the C Program for spiral traversal of a tree using recursion. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on windows 10. The program output is also shown below.

  1. /* C Program for Spiral Traversal of a given Tree */
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. struct node
  6. {
  7.     int info;
  8.     struct node* left, *right;
  9. };
  10.  
  11.  
  12. struct node* createnode(int key)
  13. {
  14.     struct node* newnode = (struct node*)malloc(sizeof(struct node));
  15.     newnode->info = key;
  16.     newnode->left = NULL;
  17.     newnode->right = NULL;
  18.  
  19.     return(newnode);
  20. }
  21.  
  22. /*
  23.  * Function to ascertain the height of a Tree
  24.  */
  25.  
  26. int heightoftree(struct node* root)
  27. {
  28.     int max;
  29.  
  30.     if (root!=NULL)
  31.     {
  32.         /*Finding the height of left subtree.*/
  33.         int leftsubtree = heightoftree(root->left); 
  34.  
  35.         /*Finding the height of right subtree.*/
  36.         int rightsubtree = heightoftree(root->right); 
  37.  
  38.         if (leftsubtree > rightsubtree)
  39.         {
  40.             max = leftsubtree + 1;
  41.             return max;
  42.         }
  43.         else
  44.         {
  45.             max = rightsubtree + 1;
  46.             return max;
  47.         }
  48.     }
  49. }
  50.  
  51. /*
  52.  * Function to print all the nodes left to right of the current level
  53.  */
  54.  
  55. void left_to_right(struct node* root, int level)
  56. {
  57.     if (root != NULL)
  58.     {
  59.         if (level == 1)
  60.         {
  61.             printf("%d ", root->info);
  62.         }
  63.  
  64.         else if (level > 1)
  65.         {
  66.             left_to_right(root->left, level-1);
  67.             left_to_right(root->right, level-1);
  68.         }
  69.     }
  70. }
  71.  
  72. void right_to_left(struct node *root, int level)
  73. {
  74.     if(root!=NULL)
  75.     {
  76.         if(level==1)
  77.         {
  78.             printf("%d ", root->info);
  79.         }
  80.         else
  81.         {
  82.             right_to_left(root->right, level-1);
  83.             right_to_left(root->left, level-1);
  84.         }
  85.     }
  86. }
  87.  
  88.  
  89. /*
  90.  * Main Function
  91.  */
  92.  
  93. int main()
  94. {
  95.     int flag = 0;
  96.     struct node *newnode = createnode(25);
  97.     newnode->left = createnode(27);
  98.     newnode->right = createnode(19);
  99.     newnode->left->left = createnode(17);
  100.     newnode->left->right = createnode(91);
  101.     newnode->right->left = createnode(13);
  102.     newnode->right->right = createnode(55);
  103.  
  104.     /* Sample Tree 1- Balanced Tree
  105.     
  106.     
  107.                     25
  108.                   /    \
  109.                  27     19
  110.                 / \     / \
  111.               17  91   13 55
  112.     */
  113.  
  114.     printf("Spiral Traversal of Tree 1 is \n");
  115.  
  116.     int i;
  117.     int height = heightoftree(newnode);
  118.     for(i = 1; i <= height; i++)
  119.     {
  120.         if(i%2 != 0)
  121.         {   
  122.             flag = 0;
  123.             left_to_right(newnode,i);
  124.         }
  125.  
  126.         if(i%2 == 0)
  127.         {
  128.             flag = 1;
  129.             right_to_left(newnode,i);
  130.         }
  131.     }
  132.  
  133.     struct node *node = createnode(1);
  134.     node->right = createnode(2);
  135.     node->right->right = createnode(3);
  136.     node->right->right->right = createnode(4);
  137.     node->right->right->right->right = createnode(5);
  138.     node->left = createnode(13);
  139.  
  140.     /* Sample Tree 2-  Unbalanced Tree
  141.     	  
  142.                    1
  143.                 /     \
  144.                13      2
  145.                         \
  146.                          3
  147.                           \
  148.                            4
  149.                             \
  150.                              5
  151.     */
  152.  
  153.     printf("\n\nSpiral Traversal of Tree 2 is \n");
  154.  
  155.     height = heightoftree(node);
  156.     for(i = 1; i <= height; i++)
  157.     {
  158.         if(i%2 != 0)
  159.         {
  160.             flag = 0;
  161.             left_to_right(node,i);
  162.         }
  163.  
  164.         if(i%2 == 0)
  165.         {
  166.             flag = 1;
  167.             right_to_left(node,i);
  168.         }
  169.     }
  170.  
  171.     struct node *root = createnode(15);
  172.  
  173.     /* Sample Tree 3- Tree having just one root node.
  174.  
  175.  
  176.                    15                
  177.  
  178.     */
  179.  
  180.    printf("\n\nSpiral Traversal of Tree 3 is \n");
  181.  
  182.     height = heightoftree(root);
  183.     for(i = 1; i <= height; i++)
  184.     {
  185.         if(i%2 != 0)
  186.         {
  187.             flag = 0;
  188.             left_to_right(root,i);
  189.         }
  190.  
  191.         if(i%2 == 0)
  192.         {
  193.             flag = 1;
  194.             right_to_left(root,i);
  195.         }
  196.     }
  197.     return 0;
  198. }
Program Explanation

1. First of all we must know how to traverse a given tree using level order traversal. In Level Order Traversal we traverse all the nodes from left to right level by level, we print the nodes at level 1 followed by level 2 and so on.
2. Here we have created two functions that traverse all the nodes level by level from left to right, as well as right to left.
3. We first traverse the root node using left_to_right() function, then the nodes of next level using right_to_left() function.
4. To call both the functions alternatively we have taken a flag, whose value keeps on updating between 0 and 1 as the functions are called.
5. We can also check on the basis of value of iterator in the loop in which both the functions are called, if the value of iterator is even, right_to_left() function is called, but if it is odd left_to_right() function is called.

advertisement
Runtime Test Cases
Spiral Traversal of Tree 1 is
25 19 27 17 91 13 55
 
Spiral Traversal of Tree 2 is
1 2 13 3 4 5
 
Spiral Traversal of Tree 3 is
15

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

advertisement
If you wish to look at programming examples on all topics, go to C Programming Examples.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.