Height of a binary tree in C++

In this tutorial, we will learn what a binary tree is, what is its height and also how to implement it using C++.

A binary tree is a finite set of elements(can be empty) from which one node is called the root node and the remaining elements are divided as left sub-tree and right sub-tree.

The height of a binary tree is the maximum level of the tree. The root node is always at level 1 and the level of any other node is parent level plus 1.

Algorithm to find the height of a binary tree in C++

Height(root)

1. Initialize h=0
2. if the root is not NULL
   -find the height of left sub-tree
   -find the height of right sub-tree
   -initialize maxHeight with the maximum of the heights of left and right sub-trees
   -assign h=maxHeight + 1
3. Return h

Implementation in C++

Below is our C++ program to find the height of a binary tree:

#include<iostream>
using namespace std;

// structure of node
struct Node
{
  Node *left; // Pointer to left sub-tree 
  int element; // Value 
  Node *right; // Pointer to right sub-tree 
  Node(int theElement,Node *theLeft,Node *theRight)
  {
    element = theElement;
    left = theLeft;
    right = theRight;
  }
};

int height(Node *root)
{
  int h = 0;
  if(root != NULL)
  {
    int lHeight = height(root->left);
    int rHeight = height(root->right);
    int maxHeight = max(lHeight,rHeight);
    h = maxHeight + 1;
  }
  return h;
}

int main()
{
  // creating a binary tree with 5 nodes
  Node *n1,*n2,*n3,*n4,*n5;
  n1 = new Node(5,NULL,NULL);
  n2 = new Node(7,NULL,NULL);
  n3 = new Node(6,n1,n2);
  n4 = new Node(9,NULL,NULL);
  n5 = new Node(3,n3,n4);
  
  cout << "Height of the tree is " << height(n5) << endl;
  return 0;
}

We created the nodes of the tree using a structure. Each node contains a pointer to the left sub-tree, a variable to store the value and a pointer to the right sub-tree.

The tree we created is:

According to the above-explained algorithm we have to pass the root node to height method. So, we passed the n5 node. The height of the tree is returned.

Output:

Height of the tree is 3

You may also read,
Level of a Node in a Binary Tree in C++
Building a Binary Tree using C++ in Competitive Programming