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

- Initialize h=0
- 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 - 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

## Leave a Reply