Find diameter of a Binary Tree.

Solution #1: Diameter of a tree is the maximum distance between its any two nodes. For e.g. consider the below tree,

            5
         /      \
       2         9
     /    \      /
    1    4    7

Diameter: 5 (1-2-5-9-7 or 4-2-5-9-7)

Here is the code,

int height(struct node* root)
{
    if(root == NULL)
        return 0;

    int lh = height(root->left);
    int rh = height(root->right);

    return 1 + MAX(lh, rh);
}

int diameter(struct node* root)
{
    if(root == NULL)
        return 0;

    int lheight = height(root->left);
    int rheight = height(root->right);

    int ldia = diameter(root->left);
    int rdia = diameter(root->right);

    return MAX(1 + lheight + rheight, MAX(ldia, rdia));
}