# 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));
}
```