Diameter of a Binary Tree

Question: The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree. The diagram below shows two trees each with diameter nine, the leaves that form the ends of a longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes).

Solution:

public int getHeight(Node root) 
{
if (root == null) 
        return 0;
    return Math.max(getHeight(root.left), getHeight(root.right))+1;
}

public int Diameter(Node root) {
if (root == null) 
      return 0;

// get the left and right subtree height
int leftSubTree = getHeight(root.left);
int rightSubTree = getHeight(root.right);

// get the left diameter and right diameter recursively.
int leftDiameter = Diameter(root.left);
int rightDiameter = Diameter(root.right);

// get the max leftsubtree, rightsubtree, longest path goes through root.
return Math.max(leftSubTree+rightSubTree+1, Math.max(leftDiameter, rightDiameter));
}

Solution 2:

/*The second parameter is to store the height of tree.    Initially, we need to pass a pointer to a location with value    as 0. So, function should be used as follows:    int height = 0;    struct node *root = SomeFunctionToMakeTree();    int diameter = diameterOpt(root, &height); */ int diameterOpt(struct node *root, int* height) {   /* lh --> Height of left subtree       rh --> Height of right subtree */   int lh = 0, rh = 0;     /* ldiameter  --> diameter of left subtree       rdiameter  --> Diameter of right subtree */   int ldiameter = 0, rdiameter = 0;     if(root == NULL)   {     *height = 0;      return 0; /* diameter is also 0 */   }     /* Get the heights of left and right subtrees in lh and rh     And store the returned values in ldiameter and ldiameter */   ldiameter = diameterOpt(root->left, &lh);   rdiameter = diameterOpt(root->right, &rh);     /* Height of current node is max of heights of left and      right subtrees plus 1*/   *height = max(lh, rh) + 1;     return max(lh + rh + 1, max(ldiameter, rdiameter)); }

Time Complexity: O(n)