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:

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.

Subscribe Now: Data Structures in C Newsletter | Important Subjects Newsletters

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.

/* C Program for Spiral Traversal of a given Tree */

```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
 
```
```
struct node
```
```
{
```
```
    int info;
```
```
    struct node* left, *right;
```
```
};
```
```
 
```
```
 
```
```
struct node* createnode(int key)
```
```
{
```

    struct node* newnode = (struct node*)malloc(sizeof(struct node));

```
    newnode->info = key;
```
```
    newnode->left = NULL;
```
```
    newnode->right = NULL;
```
```
 
```
```
    return(newnode);
```
```
}
```
```
 
```
```
/*
```

 * Function to ascertain the height of a Tree

```
 */
```
```
 
```
```
int heightoftree(struct node* root)
```
```
{
```
```
    int max;
```
```
 
```
```
    if (root!=NULL)
```
```
    {
```

        /*Finding the height of left subtree.*/

        int leftsubtree = heightoftree(root->left);

```
 
```

        /*Finding the height of right subtree.*/

        int rightsubtree = heightoftree(root->right);

```
 
```
```
        if (leftsubtree > rightsubtree)
```
```
        {
```
```
            max = leftsubtree + 1;
```
```
            return max;
```
```
        }
```
```
        else
```
```
        {
```
```
            max = rightsubtree + 1;
```
```
            return max;
```
```
        }
```
```
    }
```
```
}
```
```
 
```
```
/*
```

 * Function to print all the nodes left to right of the current level

```
 */
```
```
 
```

void left_to_right(struct node* root, int level)

```
{
```
```
    if (root != NULL)
```
```
    {
```
```
        if (level == 1)
```
```
        {
```
```
            printf("%d ", root->info);
```
```
        }
```
```
 
```
```
        else if (level > 1)
```
```
        {
```

            left_to_right(root->left, level-1);

            left_to_right(root->right, level-1);

```
        }
```
```
    }
```
```
}
```
```
 
```

void right_to_left(struct node *root, int level)

```
{
```
```
    if(root!=NULL)
```
```
    {
```
```
        if(level==1)
```
```
        {
```
```
            printf("%d ", root->info);
```
```
        }
```
```
        else
```
```
        {
```

            right_to_left(root->right, level-1);

            right_to_left(root->left, level-1);

```
        }
```
```
    }
```
```
}
```
```
 
```
```
 
```
```
/*
```
```
 * Main Function
```
```
 */
```
```
 
```
```
int main()
```
```
{
```
```
    int flag = 0;
```

    struct node *newnode = createnode(25);

```
    newnode->left = createnode(27);
```
```
    newnode->right = createnode(19);
```

    newnode->left->left = createnode(17);

    newnode->left->right = createnode(91);

    newnode->right->left = createnode(13);

    newnode->right->right = createnode(55);

```
 
```
```
    /* Sample Tree 1- Balanced Tree
```
```
    
```
```
    
```
```
                    25
```
```
                  /    \
```
```
                 27     19
```
```
                / \     / \
```
```
              17  91   13 55
```
```
    */
```
```
 
```

    printf("Spiral Traversal of Tree 1 is \n");

```
 
```
```
    int i;
```
```
    int height = heightoftree(newnode);
```
```
    for(i = 1; i <= height; i++)
```
```
    {
```
```
        if(i%2 != 0)
```
```
        {   
```
```
            flag = 0;
```
```
            left_to_right(newnode,i);
```
```
        }
```
```
 
```
```
        if(i%2 == 0)
```
```
        {
```
```
            flag = 1;
```
```
            right_to_left(newnode,i);
```
```
        }
```
```
    }
```
```
 
```
```
    struct node *node = createnode(1);
```
```
    node->right = createnode(2);
```
```
    node->right->right = createnode(3);
```

    node->right->right->right = createnode(4);

    node->right->right->right->right = createnode(5);

```
    node->left = createnode(13);
```
```
 
```
```
    /* Sample Tree 2-  Unbalanced Tree
```
```
    	  
```
```
                   1
```
```
                /     \
```
```
               13      2
```
```
                        \
```
```
                         3
```
```
                          \
```
```
                           4
```
```
                            \
```
```
                             5
```
```
    */
```
```
 
```

    printf("\n\nSpiral Traversal of Tree 2 is \n");

```
 
```
```
    height = heightoftree(node);
```
```
    for(i = 1; i <= height; i++)
```
```
    {
```
```
        if(i%2 != 0)
```
```
        {
```
```
            flag = 0;
```
```
            left_to_right(node,i);
```
```
        }
```
```
 
```
```
        if(i%2 == 0)
```
```
        {
```
```
            flag = 1;
```
```
            right_to_left(node,i);
```
```
        }
```
```
    }
```
```
 
```
```
    struct node *root = createnode(15);
```
```
 
```

    /* Sample Tree 3- Tree having just one root node.

```
 
```
```
 
```
```
                   15                
```
```
 
```
```
    */
```
```
 
```

   printf("\n\nSpiral Traversal of Tree 3 is \n");

```
 
```
```
    height = heightoftree(root);
```
```
    for(i = 1; i <= height; i++)
```
```
    {
```
```
        if(i%2 != 0)
```
```
        {
```
```
            flag = 0;
```
```
            left_to_right(root,i);
```
```
        }
```
```
 
```
```
        if(i%2 == 0)
```
```
        {
```
```
            flag = 1;
```
```
            right_to_left(root,i);
```
```
        }
```
```
    }
```
```
    return 0;
```
```
}
```

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.

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

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

If you find any mistake above, kindly email to [email protected]

« Prev - Level Order Traversal of a Tree using Recursion

» Next - C Program to Find the Lowest Common Ancestor of a Binary Search Tree

Related Posts:

Practice Computer Science MCQs
Apply for Computer Science Internship
Check Computer Science Books
Check Data Structure Books
Practice Design & Analysis of Algorithms MCQ

Recommended Articles: