Given with the binary tree, find the height of the tree.

Height of the binary tree is one more than the largest number of edges in the path from the root node to the lowest level leaf node.

## Problem Statement

We are given a **binary tree** as input and we need to find the `height of binary tree`

. In other words, we are given a binary tree and we need to calculate the **maximum depth of the binary tree**.

**Note :** The height of an empty `binary tree`

is `-1`

, and the **height** of a `binary tree`

having only one node is `0`

.

Refer to the `Example`

and `Example Explanation`

sections for more details and the `Approach`

section to understand how to find the **height of binary tree**.

## Example

**Example : 1**

The given binary tree (input) is : $[ 5, 3, 6, 2, 4 ]$.

**Tree formed is :**

```
5
/ \
3 6
/ \
2 4
```

**Output :**

`The height of binary tree is: 3.`

**Example : 2**

The given binary tree (input) is : $[ 15, 10, 20, 8, 12, 16, 25, 9 ]$.

**Tree formed is :**

```
15
/ \
10 20
/ \ / \
8 12 16 25
\
9
```

**Output :**

`The height of binary tree is: 4.`

## Example Explanation

Before getting into the explanation of the example and how to find **height of binary tree**, let us first get a brief introduction about the `binary tree`

and the `height of a binary tree`

.

A **binary tree** can be defined as a collection of `objects`

or `elements`

or `entities`

known as **nodes**. These nodes are linked together to represent a `hierarchy`

.

The top node of the hierarchy is known as the **root** node. Each node of a binary tree contains some data and it can have `at most two child nodes`

. A `root node`

can never have a `parent node`

. The nodes that do not have any `child nodes`

are termed `leaf nodes`

.

**Example :**

Now, the **height of the binary tree** is one more than the largest number of edges in the path from the `root node`

to the `lowest level leaf node`

.

In other words, we can say that the **height of binary tree** is the height of the `root node`

in the entire binary tree.

**In the example :**

```
5
/ \
3 6
/ \
2 4
```

The `root node`

is $5$ and the lowest level `leaf nodes`

are $2$ and $4$. Now, in the above example, we have the first edge from $5$ to $3$, and the second edge from $3$ to $2$. So, the **height of the binary tree** comes out to be $3$ [a number of edges + 1].

## Constraints

- $1 <=$ Number of nodes $<= 10^5$
- $1 <=$ Data of a node $<= 10^5$

In some problems, you may find the number of test cases represented by `t`

. So, we only need to call the **findHeight()** function `t`

-times.

## Approach : 1

We can easily calculate the height of binary tree using **recursion**. The idea is very simple, we will calculate the height of the current level, and recursively call the `findHeight()`

function for the `left sub-tree`

and `right sub-tree`

(if they exist).

Now, the height of the current level will be the maximum of the height of the `left sub-tree`

and the height of the `right sub-tree`

.

So, the recursive function will provide the height of the `left sub-tree`

and `right sub-tree`

and we will assign the height of the current node as the maximum of them.

We are recursively `left sub-tree`

and `right sub-tree`

because a node can have a `left`

or a `right child`

or both. Refer to the pseudo-code for a better understanding of the recursive algorithm to find the height of the binary tree.

### Algorithm :

**The pseudo-code for the same :**

**Check base case :**

- If the tree is empty, return
`-1`

as we cannot find its height. - Else, continue the further steps.

- Call the
`findHeight(root)`

function for the`left subtree`

and store the result. - Call the
`findHeight(root)`

function for the`right subtree`

and store the result. - Get the maximum of both the heights and assign the height as the result :

**height = max(left_height, right_height)**

- Return the result as
**(height + 1)**, as we need to add the current node in the total height as well.

### Code Implementation

Let us the code implementation of the same in various languages :

**C++ Code :**

```
#include <bits/stdc++.h>
using namespace std;
```*/*
**Defining a class to store a node of the binary tree. The node of the binary tree consists of data as well as the left and right pointer which points to its left and right child.
***/*
class Node {
public:
int data;
Node *left;
Node *right;
};
*/*
**A recursive function that finds the height of the binary tree by maximum height between the left and right subtree.
***/*
int findHeight(Node *node) {
*// Base case: If the tree is empty, return -1 as we cannot find its height.*
if (node == NULL)
return 0;
else {
*/* Call the findHeight() function for the left and right sub tree and store the results.
** */*
int leftHeight = findHeight(node->left);
int rightHeight = findHeight(node->right);
*// returning the (maximum + 1) as the height of the binary tree.*
if (leftHeight > rightHeight)
return (leftHeight + 1);
else
return (rightHeight + 1);
}
}
*/* A function that will add nodes to the binary tree. Its left and the right pointer will initially point to NULL as there is no child currently.
** */*
Node *addNode(int data) {
Node *newNode = new Node();
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
*// main function*
int main() {
*// creating object of the Node class.*
Node *root = addNode(1);
root->left = addNode(2);
root->right = addNode(3);
root->left->left = addNode(4);
root->left->right = addNode(5);
cout << "The height of binary tree is: " << findHeight(root);
return 0;
}

**Java Code :**

*/*
**Defining a class to store a node of the binary tree. The node of the binary tree consists of data as well as the left and right pointer which points to its left and right child.
***/*
class Node {
int data;
Node left, right;
*/* The constructor will add nodes to the binary tree. Its left and the right pointer will initially point to NULL as there is no child currently.
** */*
Node(int item) {
data = item;
left = right = null;
}
}
public class BinaryTree {
*// creating reference of the Node class.*
Node root;
*/*
** A recursive function that finds the height of the binary tree by maximum height between the left and right subtree.
** */*
int findHeight(Node node) {
*// Base case: If the tree is empty, return -1 as we cannot find its height.*
if (node == null)
return 0;
else {
*/* Call the findHeight() function for the left and right sub tree and store the results.
** */*
int leftHeight = findHeight(node.left);
int rightHeight = findHeight(node.right);
*// returning the (maximum + 1) as the height of the binary tree.*
if (leftHeight > rightHeight)
return (leftHeight + 1);
else
return (rightHeight + 1);
}
}
public static void main(String[] args) {
*// creating object of the BinaryTree class.*
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println("The height of binary tree is: " +
tree.findHeight(tree.root));
}
}

**Python Code :**

```
"""
Defining a class to store a node of the binary tree. The node of the binary tree consists of data as well as the left and right pointer which points to its left and right child.
The constructor will add nodes to the binary tree. Its left and the right pointer will initially point to None as there is no child currently.
"""
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
"""
A recursive function that finds the height of the binary tree by maximum height between the left and right subtree.
"""
def findHeight(node):
if node is None:
return 0
else:
```*# Call the findHeight() function for the left and right sub tree and store the results.*
leftHeight = findHeight(node.left)
rightHeight = findHeight(node.right)
*# returning the (maximum + 1) as the height of the binary tree*
if (leftHeight > rightHeight):
return leftHeight+1
else:
return rightHeight+1
if __name__ == "__main__":
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("The height of binary tree is: ", findHeight(root))

**Output :**

```
The height of binary tree is: 3.
```

### Time Complexity :

In the recursive approach of finding the `height of binary tree`

, we are traversing all the nodes of the binary tree. So, the **time complexity** of the algorithm comes out to be $O(n)$, where `n`

is the number of nodes in the binary tree.

### Space Complexity :

In the above code, we are not using any `extra space`

but there is recursive calls of the `findHeight()`

function. So, the **space complexity** comes out to be $O(n)$ as well.

## Approach : 2

Another approach to finding the `height of the binary tree`

is to perform the **Bread First Search** (BFS) or the `level order traversal`

of the binary tree.

We will keep on incrementing the height when we advance to the next level. For performing the `level order traversal`

, we need to use the **queue data structure**.

The idea is quite simple, we would take a queue and insert the `root node`

into it and initialize a `height`

variable.

Now, we would remove a `node`

from the **queue** (dequeue) and explore its `left`

and `right child`

, after the exploration, we will increment the height counter by one as each exploration denotes that the current level is done and we should move to the next level.**Note :** The `level order traversal`

way of finding the height of the binary tree is also known as the **iterative** way.

Refer to the `pseudo-code`

provided below for a better understanding.

### Algorithm :

**The pseudo-code for the same :**

- Initialize a
`queue`

and a`height`

variable. - Insert the
`root node`

into the queue. - Remove all the nodes that are currently present in the queue.
- Add all the
`children nodes`

i.e.**left**or**right child**(if present) and increment the height counter by`1`

. - After all the nodes are explored (i.e. the queue becomes empty), return height as result.

### Code Implementation

Let us the code implementation of the same in various languages :

**C++ Code :**

```
#include <bits/stdc++.h>
using namespace std;
```*/*
**Defining a class to store a node of the binary tree. The node of the binary tree consists of data as well as left and right pointer which points to its left and right child.
***/*
class Node {
public:
int data;
Node *left;
Node *right;
};
*/*
**A function that finds the height of the binary tree by maximum height between the left and right subtree.
***/*
int findHeight(Node *root) {
*// Initialize a queue and a height variable.*
int height = 0;
queue<Node *> q;
*// Insert the root node into the queue and a null to mark last*
q.push(root);
q.push(NULL);
*// running the discussed steps until the queue becomes empty*
while (!q.empty()) {
*// removing the node from the queue.*
Node *temp = q.front();
q.pop();
*// if NULL is encountered, increment the height counter.*
if (temp == NULL)
height++;
*// if NULL is not encountered, explore left and right child*
if (temp != NULL) {
if (temp->left)
q.push(temp->left);
if (temp->right)
q.push(temp->right);
}
else if (!q.empty())
q.push(NULL);
}
return height;
}
*/* A function that will add nodes to the binary tree. Its left and the right pointer will initially point to NULL as there is no child currently.
** */*
Node *addNode(int data) {
Node *newNode = new Node();
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
*// main function*
int main() {
*// creating object of the Node class.*
Node *root = addNode(1);
root->left = addNode(2);
root->right = addNode(3);
root->left->left = addNode(4);
root->left->right = addNode(5);
cout << "The height of binary tree is: " << findHeight(root);
return 0;
}

**Java Code :**

```
import java.util.*;
```*/*
**Defining a class to store a node of the binary tree. The node of the binary tree consists of data as well as left and right pointer which points to its left and right child.
***/*
class Node {
int data;
Node left, right;
*/* The constructor will add nodes to the binary tree. Its left and the right pointer will initially point to NULL as there is no child currently.
** */*
Node(int item) {
data = item;
left = right = null;
}
}
public class BinaryTree {
*// creating reference of the Node class.*
Node root;
*/*
** A function that finds the height of the binary tree by maximum height between the left and right subtree.
** */*
int findHeight(Node root) {
*// Initialize a queue and a height variable.*
int height = 0;
Queue<Node> q=new LinkedList<>();
*// Insert the root node into the queue and a null to mark last*
q.add(root);
q.add(null);
*// running the discussed steps until the queue becomes empty*
while (!q.isEmpty()) {
*// removing the node from the queue.*
Node temp = q.peek();
q.remove();
*// if NULL is encountered, increment the height counter.*
if (temp == null)
height++;
*// if NULL is not encountered, explore left and right child*
if (temp != null) {
if (temp.left != null)
q.add(temp.left);
if (temp.right != null)
q.add(temp.right);
}
else if (!q.isEmpty())
q.add(null);
}
return height;
}
public static void main(String[] args) {
*// creating object of the BinaryTree class.*
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println("The height of binary tree is: " +
tree.findHeight(tree.root));
}
}

**Python Code :**

```
"""
Defining a class to store a node of the binary tree. The node of the binary tree consists of data as well as left and right pointer which points to its left and right child.
The constructor will add nodes to the binary tree. Its left and the right pointer will initially point to None as there is no child currently.
"""
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
"""
A function that finds the height of the binary tree by maximum height between the left and right subtree.
"""
def findHeight(node):
```*# Initialize a queue and a height variable.*
height = 0
q = []
*# Insert the root node into the queue and None to mark last*
q.append(root)
q.append(None)
*# running the discussed steps until the queue becomes empty*
while(len(q) > 0):
*# removing the node from the queue.*
temp = q[0]
q = q[1:]
*# if None is encountered, increment the height counter.*
if(temp == None):
height += 1
*# if None is not encountered, explore left and right child*
if(temp != None):
if(temp.left):
q.append(temp.left)
if(temp.right):
q.append(temp.right)
elif(len(q) > 0):
q.append(None)
return height
if __name__ == "__main__":
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("The height of binary tree is: ", findHeight(root))

**Output :**

```
The height of binary tree is: 3.
```

### Time Complexity :

In the iterative approach of finding the **height of binary tree**, we are traversing all the nodes of the binary tree. So, the time complexity of the algorithm comes out to be $O(n)$, where `n`

is the number of nodes in the `binary tree`

.

### Space Complexity :

In the above code, we are using `extra space`

as a queue. So, the **space complexity** comes out to be $O(n)$ as well where `n`

is the size of the `queue`

or the `number of nodes`

(inserted into the queue data structure).

## Conclusion

- A
`binary tree`

can be defined as a collection of`objects`

or`elements`

or`entities`

known as**nodes**. These nodes are linked together to represent a`hierarchy`

. - The
`height of the binary tree`

is one more than the largest number of edges in the path from the`root node`

to the`lowest level leaf node`

. - The
**recursive approach**to finding the`height of binary tree`

can be calculating the height of the current level, and recursively calling the`findHeight()`

function for the`left sub-tree`

and`right sub-tree`

(if they exist). - In the
**recursive approach**of finding the height of binary tree, the**time complexity**of the algorithm comes out to be $O(n)$, where`n`

is the number of nodes in the binary tree.

In the **recursive approach**, we are not using any `extra space`

but there is recursive calls of the `findHeight()`

function. So, the **space complexity** comes out to be $O(n)$ as well.

**Another approach**to finding the`height of the binary tree`

is to perform the**Bread First Search**(BFS) or the`level order traversal`

of the`binary tree`

. We will keep on incrementing the height when we advance to the next level.- In the
**iterative approach**of finding the`height of binary tree`

, the**time complexity**of the algorithm comes out to be $O(n)$, where`n`

is the number of nodes in the`binary tree`

. - In the
**recursive approach**, we are using`extra space`

as a queue. So, the**space complexity**comes out to be $O(n)$ as well where`n`

is the**size of the queue**or the**number of nodes**(inserted into the queue data structure).