Friday, 28 April 2017

C Program to Find the Height Or Maximum Depth of a Binary tree

The height of a node is the length of the longest downward path to a leaf from that node. So, the height or maximum depth of the tree is height of its root node. Algorithm and c program to find the maximum depth or height of a binary tree is given below.

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

  In the above example, the longest root to leaf path is   5 8 12, Therefore the height of the tree is 3



ALGORITHM:

function height(ROOT)
1.   Declare two variable: left_height,right_height
2.   If  root=NULL:
3.            return 0
4.   left_height=height(root->left)
5.   right_height=height(root->right)
6.   if  left_height>right_height:
7.             return left_height+1
8.   else:
9.             return right_height+1
10. Exit


PROGRAM:

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

int get_height(struct node *root);

int main()
{

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


   struct node *root,*temp;
   int h;

   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");
   h=height(root);
   printf("\nThe height of the Binary tree is: \n\n");
      printf("%d\n",h);
  
      return 0;
}
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