Diameter of a Tree

Definition : Diameter of a tree is the longest path between two leaf nodes in a tree.

We can see in the picture below that Diameter of the tree would be maximum of these:

i. Diameter of left subtree.
ii. Diameter of right subtree.
iii. Path that goes through the root i.e. height of left subtree + height of right subtree + 1

int diameter(struct node *root)
{
    if(root==NULL)
        return 0;
    else
    {
        int leftH  = height(root->left);
        int rightH = height (root->right);
        int leftD = diameter(root->left);
        int rightD = diameter(root->right);

        return max(max(leftD,rightD),leftH+rightH+1);
    }
}

int height(struct node *root)
{
    if(root==NULL)
        return 0;
    else
        max(height(root->left),height(root->right))+1;
}

Time Complexity : O(N^2) as time complexity of height function is O(N) and we are calling it for every node.

Optimized solution: We can reduce the time complexity to O(N) by calculating height in the diameter itself and don’t call height recursively for each node.

int diameter(struct node *root, int* height)
{

  int leftH = 0, rightH = 0;
  int leftD = 0, rightD = 0;

  if(root == NULL)
  {
    *height = 0;
     return 0;
  }

  leftD = diameter(root->left, &leftH);
  rightD = diameter(root->right, &rightH);

  *height = max(leftH, rightH) + 1;

  return max(leftH + rightH + 1, max(leftD, rightD));
}