Spiral Order Traversal of a Tree using Recursion in C++

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

Problem Description

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

Expected Input and Output

Case 1. Balanced Tree If the weight on both the sides of the root is same.

 
                    25
                  /    \
                 27     19
                / \     / \
              17  91   13  55

Output: 25 19 27 17 91 13 55

Case 2: Partially Right Skewed Tree When most of the nodes in a tree have just a right child.

Output: 1 2 13 3 4 5

Case 3- Tree having just one node

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

Output: 15

Problem Solution

1. In order to traverse the tree in spiral order, we need to print the nodes in each level first left to right, then right to left or vice versa.
2. In order to do that we have to create two functions (say f1() to go left to right) and (say f2() to go right to left), and then call both of these functions alternatively by using a flag variable or the value of iterator.

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.

```
 
```

/* Spiral Traversal of a given Tree in C++*/

```
#include<iostream>
```
```
using namespace std;
```
```
struct node
```
```
{
```
```
    int info;
```
```
    struct node* left, *right;
```
```
}*root;
```
```
 
```
```
class Tree
```
```
{
```
```
    public:
```

        struct node* createnode(int key);

        int heightoftree(struct node* root);

        void left_to_right(struct node* root, int level);

        void right_to_left(struct node *root, int level);

```
        Tree()
```
```
        {
```
```
            root = NULL;
```
```
        }
```
```
};
```

struct node* Tree :: createnode(int key)

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

 * Function to ascertain the height of a Tree

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

int Tree :: heightoftree(struct node* root)

```
{
```
```
    int maximum;
```
```
 
```
```
    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)
```
```
        {
```
```
            maximum = leftsubtree + 1;
```
```
            return maximum;
```
```
        }
```
```
        else
```
```
        {
```
```
            maximum = rightsubtree + 1;
```
```
            return maximum;
```
```
        }
```
```
    }
```
```
}
```
```
 
```
```
/*
```

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

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

void Tree :: left_to_right(struct node* root, int level)

```
{
```
```
    if (root != NULL)
```
```
    {
```
```
        if (level == 1)
```
```
        {
```
```
            cout<<root->info<<"\t";
```
```
        }
```
```
 
```
```
        else if (level > 1)
```
```
        {
```

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

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

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

void Tree :: right_to_left(struct node *root, int level)

```
{
```
```
    if(root!=NULL)
```
```
    {
```
```
        if(level==1)
```
```
        {
```
```
            cout<<root->info<<"\t";
```
```
        }
```
```
        else
```
```
        {
```

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

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

```
        }
```
```
    }
```
```
}
```
```
 
```
```
 
```
```
/*
```
```
 * Main Function
```
```
 */
```
```
 
```
```
int main()
```
```
{
```
```
    Tree t;
```

    struct node *newnode = t.createnode(25);

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

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

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

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

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

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

    cout<<"Spiral traversal of a tree 1 is \n";

```
 
```
```
    int i, flag=0;
```

    int height = t.heightoftree(newnode);

```
    for(i = 1; i <= height; i++)
```
```
    {
```
```
        if(i%2 != 0)
```
```
        {   
```
```
            flag=1;
```
```
            t.left_to_right(newnode,i);
```
```
        }
```
```
 
```
```
        if(i%2 == 0)
```
```
        {
```
```
            flag=0;
```
```
            t.right_to_left(newnode,i);
```
```
        }
```
```
    }
```
```
 
```

    struct node *node = t.createnode(1);

```
    node->right = t.createnode(2);
```

    node->right->right = t.createnode(3);

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

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

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

    cout<<"\n\nSpiral traversal of tree 2 is\n" ;

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

    /*Creating Tree 3 having just a single node */

```
 
```

    struct node *root = t.createnode(15);

```
 
```
```
 
```
```
 
```

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

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

    cout<<"\n\nSpiral traversal of tree 3 is\n";

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

Program Explanation

In order to traverse a tree in spiral order, we need to print all the nodes in a level from left to right then right to left, so the basic idea is to use level order traversal and create one more function which traverses the nodes in a level from right to left.
2. 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. Here we have created one more function which traverses the nodes in a level from 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. 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. 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 a 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.

« Prev - C++ Program to Implement Double Order Traversal of a Binary Tree

» Next - C++ Program to Create Mirror Image of a Binary Tree

Related Posts:

Check Computer Science Books
Practice Programming MCQs
Check Data Structure Books
Practice Design & Analysis of Algorithms MCQ
Practice Computer Science MCQs

Recommended Articles: