C Program to Find the Height of the Binary Tree

Last Updated on June 10, 2024 by Abhishek Sharma

Binary trees are hierarchical data structures where each node has at most two children, referred to as the left child and the right child. The height of a binary tree is the length of the longest path from the root node to any leaf node in the tree. Calculating the height of a binary tree is a fundamental operation in tree data structures and is often used in various applications involving trees.

What is the Difference between the Depth and Height of a Binary Tree?

The quantity of edges connecting a tree node to its root node is known as the node’s depth. The depth of a root node is 0.
The number of edges on the longest path from a tree node to a leaf determines the node’s height. The height of a leaf node is 0.

This blog post will address a very frequent query regarding binary trees: How can we determine the height of a binary tree?

Let’s understand it using an example.g

Consider the binary tree given below:

In the tree given above,

Height – Since there are 5 leaf nodes between the root and any of them, the height of a root node is 5.

Depth – the depth of the root node will be 0 since we are at the root node.
The longest path is coloured, i.e. 1->2->4->6->7.

The following path will be travelled to determine the binary tree’s height:

If we carefully try to observe the depth and height of 2, then as per the definition

Height – the height will be 4 (7->6->4->2)
Depth – if we compute the depth then it will be 2 (1->2).

Now, let’s understand the approach behind this.

Height of a Binary Tree

Let’s first understand the idea of a binary tree’s height. The greatest distance between any leaf node and the root node determines a binary tree’s height. Let’s start by talking about the recursive method for determining a binary tree’s height.

1. Starting from the root node, the height will initially be 0.
2. We shall recursively determine the left subtree’s height.
3. In a similar manner, we will determine the right subtree’s height.
4. I will now multiply the maximum height between the right and left subtrees by one to get the height of the current node.

Algorithm to Find the Height of the Binary Tree in C Using Recursion

• If the binary tree is empty, then return 0.
• Else
  • Get the maximum height of the left subtree recursively. Function height_of_binary_tree (tree->left-subtree)
  • Get the maximum height of the right subtree recursively. height_of_binary_tree (tree->right-subtree)
  • Get the max of maximum heights of left and right subtrees. Add 1 to it for the current node.
  • max_height = max(max_height of left subtree, maximum_height of right subtree) + 1
  • Return maximum_height.

Code Implementation

#include<stdio.h>
#include <stdlib.h>

struct node
{
int data;
struct node *left;
struct node *right;
};
struct node *newNode(int data)
{
struct node *temp = (struct node *) malloc(sizeof(struct node));
temp -> data = data;
temp -> left = NULL;
temp -> right = NULL;
return temp;
};

int height_of_binary_tree(struct node *node)
{
if(node == NULL)
return 0;
else
{
int left_side;
int right_side;
left_side = height_of_binary_tree(node -> left);
right_side = height_of_binary_tree(node -> right);
if(left_side > right_side)
{
return left_side + 1;

}
else
return right_side + 1;
}
}

void insert_node(struct node *root, int n1, int n2, char lr)
{
if(root == NULL)
return;
if(root->data == n1)
{
switch(lr)
{
case 'l':root->left = newNode(n2);
break;
case 'r': root->right = newNode(n2);
break;
}
}
else
{
insert_node(root -> left, n1, n2, lr);
insert_node(root -> right, n1, n2, lr);
}
}

void inorder(struct node *root)
{
if(root == NULL)
return;
inorder(root -> left);
printf("%d ", root->data);
inorder(root -> right);
}

int main()
{
struct node *root = NULL;
int n;
scanf("%d",&n);
while(n--)
{
char lr;
int n1,n2;
scanf("%d",&n1);
scanf("%d",&n2);
scanf("%c",&lr);
if(root == NULL)
{
root = newNode(n1);
switch(lr)
{
case 'l':root->left = newNode(n2);
break;
case 'r': root->right = newNode(n2);
break;
}
}
else
{
insert_node(root,n1,n2,lr);
}
}
inorder(root);
printf("\n");
printf("\nHeight of binary tree : %d" , height_of_binary_tree(root));
printf("\n");
return 0;
}

Conclusion
In this C program, we have implemented a function to find the height of a binary tree using recursion. Understanding how to calculate the height of a binary tree is important in various applications involving trees, such as in implementing tree-based data structures like AVL trees and in solving problems related to binary trees.

Frequently Asked Questions regarding the Height of a Binary Tree in C

Here are some of the FAQs related to Height of a Binary Tree in C:

1. What is the height of a binary tree?
The height of a binary tree is the length of the longest path from the root node to any leaf node in the tree.

2. How do you find the height of a binary tree in C?
To find the height of a binary tree in C, you can use a recursive approach. Traverse the tree recursively and calculate the height of the left and right subtrees. The height of the tree is the maximum of the heights of the left and right subtrees, plus one.

3. What is the time complexity of finding the height of a binary tree?
The time complexity of finding the height of a binary tree is O(n), where n is the number of nodes in the tree. This is because the algorithm visits each node in the tree exactly once.

4. Can a binary tree be empty?
Yes, a binary tree can be empty. The height of an empty binary tree is considered to be -1.

5. What is the difference between depth and height of a binary tree?
The depth of a node in a binary tree is the number of edges from the root node to that node. The height of a node in a binary tree is the number of edges on the longest path from that node to a leaf node.