# 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`