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