Find the height of a binary tree in C, C++ | faceprep

Program to find the height of a binary tree is discussed here. The height of a binary tree is nothing but the distance between the root node (first node) and the leaf node (last node). A binary tree has two subtrees: Left subtree and right subtree. The challenge here is to find out in which subtree is the leaf node present.

So, to find this out, we first calculate the height of the left subtree. Second, we calculate the height of the right subtree by traversing through it. Now, we find the maximum of these two heights and add 1 to it (1 is added as the root node should also be included in calculating the length). This gives us the height/depth of the binary tree.

Let us now look at an example. Below is the binary tree for which height needs to be calculated.

height of a binary tree

The height of right subtree = 4 {10, 5, 22, 7}
The height of left subtree = 3 {1, 4, 8}
Maximum (Height of right subtree, Height of left subtree) = Max (4, 3) = 4
Height of the tree = 4 + 1 (root) = 5

An algorithm to find the height of a binary tree using recursion

Height_of_binary_tree(node)

  1. If the binary tree is empty, then return 0.
  2. 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.

Program to find height of a binary tree using recursion

// C program to find the height of a binary tree

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

// C++ program to find the height of a binary tree

#include
#include
using namespace std;

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);
cout << root -> data << ” “;
inorder(root -> right);
}

int main()
{
struct node *root = NULL;
int n;
cin >> n;
while(n–)
{
char lr;
int n1,n2;
cin >> n1 >> n2;
cin >>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);
cout << endl;
cout<< “Height of the binary tree : ” << height_of_binary_tree(root) << endl;
return 0;
}

Time complexity: O(n) 

An algorithm to find the height of a binary tree (Iterative)

  1. Create a queue and push the root node to the queue.
  2. Initialize height = 0.
  3. Repeat while there are elements in the queue.
  4.       Initialize node_count = size of the queue
  5.       While(node_count > 0)
  6.           Pop nodes from the queue
  7.           Push its children to the queue
  8.           Decrement node_count
  9.       If (node_count  == 0)
  10.           Return height
  11.       Else
  12.           Increment height

C++ Program to find the height of the binary tree in iterative method

// C++ program to find the height of the binary tree iteratively

#include <bits/stdc++.h>
using namespace std;

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 *root)
{
if (root == NULL)
return 0;

queue<node *> queue1;

queue1.push(root);
int height = 0;

while (1)
{
int node_count = queue1.size();
if (node_count == 0)
return height;

height++;
while (node_count > 0)
{
node *node = queue1.front();
queue1.pop();
if (node->left != NULL)
queue1.push(node->left);
if (node->right != NULL)
queue1.push(node->right);
node_count–;
}
}
}

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);
cout << root -> data << ” “;
inorder(root -> right);
}

int main()
{
struct node *root = NULL;
int n;
cout << “\nEnter the number of edges : “;
cin >> n;
while(n–)
{
char lr;
int n1,n2;
cin >> n1 >> n2;
cin >>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);
cout << endl;
cout<< “Height of the binary tree : ” << height_of_binary_tree(root) << endl;
return 0;
}