Friday, 28 April 2017

C Program for Level Order Traversal of Binary Tree using Recursion

Trees can also be traversed in level-order. In level order traversal we visit every node of the level before going to the next level. C Program for level Order traversal of Binary tree using recursion is also given below.

Example:
                                                  5
                                                 /  \
                                               /      \
                                             8       19
                                           / \          / \
                                         /     \      /     \
                                      12    14  21    23

  Level order traversal of the above tree is:      5  8  19  12  14  21  23



ALGORITHM:

function level_order_traversal(ROOT)
1. calculate the height of the tree        
2. do For i=1 to i=h:
3.       print_given_level(ROOT,i)
4. end For

function print_given_level(ROOT,LEVEL)
1. if root=NULL:
2.      return
3. if LEVEL=1:
4.      print data of current node
5. else if LEVEL>1:
6.      print_given_level(ROOT->LEFT,LEVEL-1)
7.      print_given_level(ROOT->RIGHT,LEVEL-1)
8. EXIT

           


If you don't know how to find the height of the Binary tree, click here

PROGRAM:

#include <stdio.h>
#include <stdlib.h>
struct node
{
   int data;
   struct node *left,*right;
};

void level_order_traversal(struct node *root);
int get_height(struct node *root);
void print_given_level(struct node *root,int level);

int main()
{

      /*  Genrating the binary tree
      
                     5
                   /   \
                  /     \
                 8       19
                / \      / \
               /   \    /   \
             12    14  21    23
             
      */


   struct node *root,*temp;

   temp=(struct node*)malloc(sizeof(struct node));
   temp->data=5;
   root=temp;
   temp->left=(struct node*)malloc(sizeof(struct node));
   temp->left->data=8;
   temp->left->left=(struct node*)malloc(sizeof(struct node));
   temp->left->left->data=12;
   temp->left->left->left=temp->left->left->right=NULL;
   temp->left->right=(struct node*)malloc(sizeof(struct node));
   temp->left->right->data=14;
   temp->left->right->left=temp->left->right->right=NULL;

   temp->right=(struct node*)malloc(sizeof(struct node));
   temp->right->data=19;
   temp->right->left=(struct node*)malloc(sizeof(struct node));
   temp->right->left->data=21;
   temp->right->left->left=temp->right->left->right=NULL;
   temp->right->right=(struct node*)malloc(sizeof(struct node));
   temp->right->right->data=23;
   temp->right->right->right=temp->right->right->left=NULL;

   printf("\n\n");
   printf("\nThe level order traversal of the tree is: \n\n");

   level_order_traversal(root);
      return 0;
}
void level_order_traversal(struct node *root)
{
   int h,i;
   h=height(root);
   for(i=1;i<=h;i++)
   {
        print_given_level(root,i);
   }
}
void print_given_level(struct node *root,int level)
{
   if(root==NULL)
   {
       return;
   }
   if(level==1)
   {
        printf("%d ",root->data);
   }
   else if(level>1)
   {
          print_given_level(root->left,level-1);
          print_given_level(root->right,level-1);
   }
}
int height(struct node *root)
{
   int right_height,left_height;
   if(root==NULL)
   {
       return 0;
   }
   left_height=height(root->left);
   right_height=height(root->right);
   if(left_height>right_height)
   {
        return left_height+1;
   }
   else
   {
        return right_height+1;
   }
}


OUTPUT:







EmoticonEmoticon