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

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

}

You might also like…

C program to create a Binary Search Tree | Part1

Kth Largest and Smallest in Binary Search Tree | Part2

Follow For Instant Updates

Join WhatsApp Group: link
Join our Telegram Channel: link
Like our Facebook Page:  link
Subscribe to our Youtube channel: link

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.
0 0 votes
Article Rating
Subscribe
Notify of
guest
5.4K Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
5.4K
0
Would love your thoughts, please comment.x
()
x