# Height of a Binary Tree

By | October 23, 2015

# Height of a Binary Tree

Given a Binary Tree, we need to print the height of the tree (or the maximum depth).

Example:

```             80
/     \
60      110
/  \    /
35   40  85
/  \
64   72
```

For the tree shown above, the output should be 4.

height of tree = max { height of left subtree ,  height of right subtree } + 1

height() is a recursive function that return the height of the tree

### Finding the Depth (or height) of a Binary Tree solution:

Video Explanation:

#### Algorithm to find height of a Binary Tree :

1. If the root is null ( the tree is empty) then return 0.
2. Else
1. Find the height of the left subtree
height(root->left).
2. Find the size of the right subtree
height(root->right).
3. Return max(height(root->left) + height(root->right)) + 1

#### Depth of Binary Tree solution code:

Here is the working code:

```#include <bits/stdc++.h>
using namespace std;

/*Structure for each node of the tree*/
struct node
{
int data;
node *right,*left;
};

/*Function that allocates memory for
each new node and initialises it*/
node * newNode(int data)
{
node *temp=new node;
temp->data=data;
temp->left=NULL;
temp->right=NULL;

return temp;
}

/*The function that returns the number of nodes
int the tree*/
int height(node *root)
{
/*Base case when the tree is NULL*/
if(!root)
return 0;
/*Calculating recursively for left subtree
right subtree and adding 1 to it for present node*/
return (max(height(root->left),height(root->right)) +1);
}

int main()
{
/*
We are making the following tree
80
/    \
60      110
/  \    /
35   40  85
/  \
64  72
*/
node *root               = newNode(80);
root->left               = newNode(60);
root->right              = newNode(110);
root->left->left         = newNode(35);
root->left->right        = newNode(40);
root->right->left 	   = newNode(85);
root->left->left->left   = newNode(64);
root->left->left->right  = newNode(72);

cout<<"height of the tree is \n"<<height(root);

return 0;
}```

Output:

```height of the tree is
4```

Time Complexity: O(n) as all nodes are visited once