C Program to Find the Height of the Binary Tree

Last Updated on May 9, 2023 by Prepbytes

Operating systems and server architecture use binary trees as an essential data structure in computer science. Binary trees may significantly decrease the complexity of many kinds of problems.

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
We discussed how to find a binary tree’s height and depth in this post. This is a straightforward binary tree recursive problem that can be resolved via recursion. This idea is crucial and has applicability to various issues using the binary tree data structure.

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

Q1. What is a binary search tree?
Ans. A tree used to retrieve, sort, and search data is known as a binary search tree, or BST. The nodes are placed in a certain order in this non-linear data structure.

• A node’s left subtree contains nodes that are only less than its key.
• A node’s right subtree contains nodes that are only greater than the key of that node.
• In the Binary Search Tree, duplicate keys are not permitted since each node has unique keys.
• Binary search trees must also be used for the left and right subtrees.

Q2. Is DFS & preorder traversal the same?
Ans. Another DFS variation is preorder traversal. Pre-order traversal is comparable to depth-first search (DFS), which explores the search tree as much as possible before moving on to the next sibling.

Q3. What if the height of a binary tree is 6?
Ans. As we need the height of a tree to be 6, and we have seven distinct numbers. Other than the root node we have 2 options at each level either node is a left node or a right node only. Therefore, the total number of BSTs =1×2×2×2×2×2×2=1×26=1×64=64 Answer.