Find the Maximum Depth or Height of given Binary Tree

 

Given a binary tree, the task is to find the height of the tree. The height of the tree is the number of vertices in the tree from the root to the deepest node. 

Note: The height of an empty tree is 0 and the height of a tree with single node is 1.

Example of Binary Tree

Recursively calculate the height of the left and the right subtrees of a node and assign height to the node as max of the heights of two children plus 1. See below the pseudo code and program for details.

maxDepth(‘1’) = max(maxDepth(‘2’), maxDepth(‘3’)) + 1 = 2 + 1

because recursively 
maxDepth(‘2’) =  max (maxDepth(‘4’), maxDepth(‘5’)) + 1 = 1 + 1 and  (as height of both ‘4’ and ‘5’ are 1)
maxDepth(‘3’) = 1

class node {
public:
	int data;
	node* left;
	node* right;
};

int maxDepth(node* node) {
	if (node == NULL) return 0;

	int leftDepth = maxDepth(node->left);
	int rightDepth = maxDepth(node->right);

	if (leftDepth > rightDepth)
	{
		return (leftDepth + 1);
	}
	else {
		return (rightDepth + 1);
	}
}