- 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 : 3In 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