C++ Program for Spiral Traversal of a Tree using recursion

«
»

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.

advertisement
 
                    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.

 
                     1
                    / \
                   13  2
                        \
                         3
                          \
                           4
                            \
                             5

Output: 1 2 13 3 4 5

advertisement

Case 3- Tree having just one node

                    15

Output: 15

advertisement
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.

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

advertisement
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 Reference Books in C++ Programming, Data Structures and Algorithms.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn