Diameter of a tree

The function below returns the diameter of a tree. A tree's diameter is defined after the function. Write a recurrence for this function and solve it yielding the running time using big-Oh in terms of the number of nodes in a tree.


int diameter(Tree * t)
// post: return diameter of t
{
    if (t == 0) return 0;

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

    int ldiameter = diameter(tree->left);
    int rdiameter = diameter(tree->right);

    return max(lheight + rheight + 1,
      max(ldiameter,rdiameter));
}

The following function returns the height of a tree (the number of nodes on the longest root-to-leaf path).

    int height(Tree * t)
    // postcondition: returns height of tree with root t
    {
        if (t == 0)
        {
            return 0;
        }
        else
        {
            return 1 + max(height(t->left),height(t->right));
        }
    }