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

- If the root is null ( the tree is empty) then return 0.
- Else
- Find the height of the left subtree

height(root->left). - Find the size of the right subtree

height(root->right). - Return max(height(root->left) + height(root->right)) + 1

- Find the height of the left subtree

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