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
#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); }