Maximum Height (Depth) of a Binary Tree

The maximum height of a binary tree is defined as the number of nodes along the path from the root node to the deepest leaf node. Note that the maximum height of an empty tree is 0.

Recursive Solution:
We can solve this easily using recursion. Why? Because each of the leftChild and rightChild of a node is a sub-tree itself. We first compute the max height of left sub-tree, then compute the max height of right sub-tree. Therefore, the max height of the current node is the greater of the two max heights + 1. For the base case, the current node is NULL, we return zero. NULL signifies there is no tree, therefore its max height is zero.

int maxHeight(BinaryTree *p)
{
     if (!p) return 0;

     int left_height = maxHeight(p->left);
     int right_height = maxHeight(p->right);

     return (left_height > right_height) ? left_height + 1 : right_height + 1;
}