C program to find Height of Binary Tree | Amazon

C program to find Height of Binary Tree | Amazon

Question

Write a C program to find height of binary tree. The height of the root node is 0 and increase by one at each level. This question is asked in MakeMyTrip, Amazon, Snapdeal, Vmware etc.

 

Logic

  • Create a Binary tree as given above.
  • We use leftSubTree() to find the height of the left side tree. In that, we pass the pointer to the left child of the root.
  • We use rightSubTree() to find the height of the right side tree. In that, we pass the pointer to the right child of the root.
  • To find the height, static variables Lcount and Rcount are used.
  • A Static variable is able to retain its value between different function calls.
  • The static variable is initialized only once.
  • Finally, Compare the height of the left (=2) and right (=3) subtree and print the largest.

Program

[code lang=”c”]
#include<stdio.h>
struct tree
{
struct tree* left;
struct tree* right;
int data;
};

/*function to create new Node*/
struct tree* createNode(int data)
{
struct tree* temp = (struct tree*)malloc(sizeof(struct tree));
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}

/*function to find height of leftsubtree*/
int leftSubTree(struct tree* root)
{
/*static is used to make Lcount common for all the function calls*/
static int Lcount=0; //executed only first time
if(root!=NULL)
{
Lcount++;
leftSubTree(root->left);
leftSubTree(root->right);
}
return Lcount; //returns the height of leftsubtree
}

/*function to find height of rightsubtree*/
int rightSubTree(struct tree* root)
{
static int Rcount=0; //executed only first time
if(root!=NULL)
{
Rcount++;
rightSubTree(root->left);
rightSubTree(root->right);
}
return Rcount; //returns the height of rightsubtree

}

int main()
{
struct tree* root = NULL;
int Lheight,Rheight;

/*Creating tree*/
root = createNode(5);
root->left = createNode(10);
root->right = createNode(15);
root->left->left = createNode(20);
root->right->right = createNode(23);
root->right->right->left = createNode(30);

/*Passing leftchild of root to leftSubTree function*/
Lheight = leftSubTree(root->left);
/*Passing rightchild of root to rightSubTree function*/
Rheight = rightSubTree(root->right);

printf("%d %d\n",Lheight,Rheight);

if(Lheight>Rheight)
printf("Height is %d",Lheight);
else
printf("Height is %d",Rheight);

}
[/code]

You might also like…

C program to create a Binary Search Tree | Part1

Kth Largest and Smallest in Binary Search Tree | Part2

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.

Leave a Reply

Your email address will not be published. Required fields are marked *