C Program to Find the Height of Tree using Recursion

This is a C Program to find the Height of a Tree using Recursion.

Problem Description

We are given a tree, and we have to write a C program to find out the height of that tree using recursion. We have to create a recursive function which takes in root of the tree as input and returns height of the tree as output.

Expected Input and Output

Case 1. Tree having same weight on both the sides of root node (A Balanced Tree).
For example:

If the input tree is       
                    25
                  /    \
                 27     19
                / \     / \
              17  91   13 55
the height of the tree here will be 3

Case 2. Tree having only right children at every level (Right Skewed Tree). A right skewed tree is one in which all the nodes just have a right child at all the levels. For example:

 If the input tree is      
                    1
                     \
                      2
                       \
                        3
                         \
                          4
                           \
                            5 
the height of the tree here will be 5

Case 3. Tree having just one node. For example:

 If the input tree is      
              15   
the height of the tree here will be 1

Problem Solution

We can easily find the height of the tree using recursion. We need to create a function which takes in root of the tree as parameter. After that we will compute the height of left subtree and right subtree and whichever is greater will be the maximum height of subtree.

Subscribe Now: Data Structures in C Newsletter | Important Subjects Newsletters

Program/Source Code

Here is source code of the C Program to find the Height of a Tree using Recursion. The program is successfully compiled and tested using Codeblocks gnu/GCC compiler on windows 10. The program output is also shown below.

/* C Program to find the height of a Tree */

```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
 
```
```
struct node
```
```
{
```
```
    int info;
```
```
    struct node* left, *right;
```
```
};
```
```
 
```
```
/*
```
```
 * Function to create new nodes
```
```
 */
```
```
 
```
```
struct node* createnode(int key)
```
```
{
```

    struct node* newnode = (struct node*)malloc(sizeof(struct node));

```
    newnode->info = key;
```
```
    newnode->left = NULL;
```
```
    newnode->right = NULL;
```
```
 
```
```
    return(newnode);
```
```
}
```
```
 
```
```
/*
```

 * Function to ascertain the height of a Tree

```
 */
```
```
 
```
```
int heightoftree(struct node* root)
```
```
{
```
```
    int max;
```
```
 
```
```
    if (root!=NULL)
```
```
    {
```

        /*Finding the height of left subtree.*/

        int leftsubtree = heightoftree(root->left);

        /*Finding the height of right subtree.*/

        int rightsubtree = heightoftree(root->right);

```
        if (leftsubtree > rightsubtree)
```
```
        {
```
```
            max = leftsubtree + 1;
```
```
            return max;
```
```
        }
```
```
        else
```
```
        {
```
```
            max = rightsubtree + 1;
```
```
            return max;
```
```
        }
```
```
    }
```
```
}
```
```
 
```
```
/*
```
```
 * Main Function
```
```
 */
```
```
 
```
```
int main()
```
```
{
```
```
   /* Creating first Tree.*/
```
```
 
```

    struct node *newnode = createnode(25);

```
    newnode->left = createnode(27);
```
```
    newnode->right = createnode(19);
```

    newnode->left->left = createnode(17);

    newnode->left->right = createnode(91);

    newnode->right->left = createnode(13);

    newnode->right->right = createnode(55);

```
 
```
```
    /* Sample Tree 1- Balanced Tree
```
```
 
```
```
 
```
```
                    25
```
```
                  /    \
```
```
                 27     19
```
```
                / \     / \
```
```
              17  91   13 55
```
```
 
```
```
 
```
```
    */
```

    printf("Height of the first Tree is\t%d\n",heightoftree(newnode));

```
 
```
```
    /* Creating second Tree.*/
```
```
 
```
```
    struct node *node = createnode(1);
```
```
    node->right = createnode(2);
```
```
    node->right->right = createnode(3);
```

    node->right->right->right = createnode(4);

    node->right->right->right->right = createnode(5);

```
 
```

    /* Sample Tree 2-   Right Skewed Tree (Unbalanced).

```
 
```
```
                    1
```
```
                     \
```
```
                      2
```
```
                       \
```
```
                        3
```
```
                         \
```
```
                          4
```
```
                           \
```
```
                            5
```
```
    */
```
```
 
```

    printf("\nHeight of the second Tree is\t%d\n",heightoftree(node));

```
 
```
```
    /*Creating third Tree. */
```
```
 
```
```
    struct node *root = createnode(15);
```
```
 
```

    /* Sample Tree 3-  Tree having just one root node.

```
 
```
```
                   15
```
```
 
```
```
    */
```
```
 
```

    printf("\nHeight of the third Tree is\t%d",heightoftree(root));

```
 
```
```
    return 0;
```
```
}
```

Program Explanation

1. We have created three trees, considering different cases. Tree can be balanced, unbalanced or one having just a single node.
2. Irrespective of the type of tree, the function heightoftree(struct node* root) will always return the correct height of the tree whether be it a balanced tree, unbalanced tree or one having a single node.
3. heightoftree(struct node* root) function takes in root of the tree as parameter. After passing root of the tree we have to check whether the tree exists or not.
4. If the root node of the tree is not NULL, only then we can compute the height of a tree.
5. We have to calculate maximum height of the subtree, for which we have called this function twice recursively by passing root->left then root->right.
6. heightoftree(root->left) will return the height of the left subtree, similarly heightoftree(root->right) will return height of the right subtree. After that we will add 1 to whichever of them is greater because in order to compute the total height of the tree, we need to consider the root node as well, that is why we have added 1.

Runtime Test Cases

Height of the first Tree is     3
 
Height of the second Tree is    5
 
Height of the third Tree is     1

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.

« Prev - C Program to Create Mirror Image of Binary Tree

» Next - C Program to Implement Threaded Binary Tree

Related Posts:

Recommended Articles: