# Find height of a binary tree using recursive approach | Set 1

In this article, we are going to see **how to find height of a binary tree recursively?** Height of a Binary tree is basically the path length from root to the deepest leaf node. Here, we have discussed the approach and provided implementation both in C & C++.

Submitted by Radib Kar, on July 30, 2020

## What is height of a binary tree?

The **height of a binary tree** can be defined in many ways. We are giving two most relevant definitions which can help to solve the problem, i.e. to find the height of a binary tree.

- Height of a binary tree can be thought of the longest path length from root to the deepest leaf.
- In other word height of a binary tree can be defined as 1+ maximum (height of left subtree, height of right subtree) which is of course a recursive definition.

Both of the above definition helps to find the height of the binary tree, but in this tutorial we will focus only on the second definition which helps to find the height recursively. We have also discussed the first definition is another tutorial here (Find Height of a Binary Tree using level order tree traversal | set 2

So,

** Height (original tree)** = 1+

**where Height is the recursive function and takes input a Tree root.**

*maximum(Height(left subtree)+ Height(right subtree))*The details of the above recursive function can be written as:

Function height( TreeNode root) returns int which is the height int height(TreeNode root): //base case if root is NULL return 0 //1 is for the height of root return 1+ maximum (height(root->left, height(root->right))

Let check how the above algorithm is working on the below example:

Do define a node we will use its value.

So in the main function, we call height(1) //1 is root Function height(1): Root(1) is not NULL So call 1+ max(height(1->left) +height(1->right)) So it calls height(1->left) first Function height(2): Root(1) is not NULL So call 1+ max(height(2->left) +height(2->right)) So it calls height(2->left) first Function height(4): Root(4) is not NULL So call 1+ max(height(4->left) +height(4->right)) So it calls height(4->left) first Function height(NULL): Root(NULL) is NULL so return 0 Return goes back to Function height(4) Now it calls height(4->height) Function height(NULL): Root(NULL) is NULL so return 0 So return again goes back to Function height(4) It returns 1+max(0,0)=1 back to function height(2) So now it calls height(2->right) Function height(NULL): Root(NULL) is NULL so return 0 So now, Function height(2) return 1+max(1,0)=2 to function height(1->left) Now in Function height(1) we have the height of its left subtree and that's 2 Now it will calls height(1->right) to find its right subtree height which we can find similar way and the value would be 5 So height of the tree is1+max(2,5)=6

**That's how recursion solves the problem and below is the C & C++ implementations.**

**C Implementation:**

#include <stdio.h> #include <stdlib.h> struct tree { int val; struct tree* left; struct tree* right; }; typedef struct tree TreeNode; TreeNode* newTree(int data) { // Allocate memory for new node TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); // Assign data to this node val root->val = data; // Initialize left and right children as NULL root->left = NULL; root->right = NULL; return (root); } int max(int a, int b) { return (a >= b) ? a : b; } //to find the height int height(TreeNode* root) { //base case if (root == NULL) return 0; //tree height = 1+maximum //(left subtree height,right subtree height) return 1 + max(height(root->left), height(root->right)); } int main() { //building the tree TreeNode* t = newTree(1); t->left = newTree(2); t->left->left = newTree(4); t->right = newTree(3); t->right->left = newTree(5); t->right->right = newTree(6); t->right->left->left = newTree(7); t->right->right->right = newTree(8); t->right->right->right->right = newTree(9); t->right->right->right->right->left = newTree(10); printf("Height of the tree is: %d", height(t)); return 0; }

**Output:**

Height of the tree is: 6

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; // tree node is defined class TreeNode { public: int val; TreeNode* left; TreeNode* right; TreeNode(int data) { val = data; left = NULL; right = NULL; } }; int height(TreeNode* root) { //base case if (root == NULL) return 0; //tree height = 1+maximum //(left subtree height,right subtree height) return 1 + max(height(root->left), height(root->right)); } int main() { //building the tree TreeNode* t = new TreeNode(1); t->left = new TreeNode(2); t->left->left = new TreeNode(4); t->right = new TreeNode(3); t->right->left = new TreeNode(5); t->right->right = new TreeNode(6); t->right->left->left = new TreeNode(7); t->right->right->right = new TreeNode(8); t->right->right->right->right = new TreeNode(9); t->right->right->right->right->left = new TreeNode(10); cout << "height of the tree is :" << height(t); return 0; }

**Output:**

height of the tree is :6

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.