# Program to Find Maximum Depth or Height of a Binary Tree

• Write a C program to find maximum depth of a binary tree.
• Function to print height of a binary tree.

The height of a tree is the number of nodes from the root node to the deepest leaf. To find the height of a binary tree, we will take maximum of left and right sub tree height + 1. For Example:

```Given Binary Tree
1  <--Root
/ \
2    3
/    / \
4    8   6
Height of Binary Tree : 3
```
In this program, we will use recursion to find the height of a binary tree. Finding the height of binary tree can be divided to two sub problems of finding the height of left and right sub tree.

Height of Tree = Maximum of(left Sub tree height , right sub tree height) + 1;

Algorithm to find maximum depth of a binary tree
Let "root" be the pointer to a root node of a binary tree and "getHeight" function returns height of tree.
• Recursion termination condition : If root is equal to NULL, return 0;
• Recursively, find the height of left sub tree(getHeight(root->left). Let it be leftHeight.
• Recursively, find the height of right sub tree(getHeight(root->right). Let it be rightHeight.
• Return Maximum of(leftHeight, rightHeight) + 1

In this program, we will use "getHeight" function which takes pointer to a root node of binary tree and returns it's height by implementing above algorithm.

```int getHeight(struct node *root){
int leftHeight, rightHeight;
if(root == NULL)
return 0;
leftHeight = getHeight(root->left);
rightHeight = getHeight(root->right);

return getMax(leftHeight, rightHeight) + 1;
}
```

## C program to find height of a binary tree

```#include <stdio.h>

struct node {
int data;
struct node *left;
struct node *right;
};

struct node* getNewNode(int data) {
/* dynamically allocate memory for a new node */
struct node* newNode = (struct node*)malloc(sizeof(struct node));

/* populate data in new Node */
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;

return newNode;
}

/*
This function returns below
1
/ \
2    3
/ \  / \
4  5 6  7
/
8
*/
struct node* generateBTree(){
// Root Node
struct node* root =  getNewNode(1);
// Level 2 nodes
root->left = getNewNode(2);
root->right = getNewNode(3);
// Level 3 nodes
root->left->left = getNewNode(4);
root->left->right = getNewNode(5);
root->right->left = getNewNode(6);
root->right->right = getNewNode(7);
// Level 4 nodes
root->left->left->left = getNewNode(8);

return root;

}
/* Returns maximum of two given numbers */
int getMax(int a, int b){
if(a >= b)
return a;
else
return b;
}
/*
Returns total number of nodes(size) in a bianry tree
getHeight(root) = Maximum of (getHeight(left-subTree),
getHeight(right-subTree)) + 1;
*/
int getHeight(struct node *root){
int leftHeight, rightHeight;
if(root == NULL)
return 0;
leftHeight = getHeight(root->left);
rightHeight = getHeight(root->right);

return getMax(leftHeight, rightHeight) + 1;
}

int main() {
struct node *root = generateBTree();

printf("Height of Tree = %d", getHeight(root));

getchar();
return 0;
}
```
Output
```Height of Tree = 4
```