ALGO: What is the diameter of a tree and what is the way to find it ?

Question

1,1,2,2,2,6,6,6,7,7,7,7,7,7,7,8,8,9,9,9

Example:
Input = 1 Output=0 (First index of 1).
Input = 2 Output=2 (First index of 2).
Input = 6 Output= 5 (First index of 6).
Input = 7 Output= 8 (First index of 7).
Input = 8 Output=15 (First index of 8).
Input = 9 Output=17 (First index of 9).

Answer 1

**

Diam­e­ter of tree:

**
A longest path or route between any two nodes in a tree. The path may or may not for through the root.
And we find diameter as:
Maximum(Diameter of left sub­tree, Diam­e­ter of right sub­tree, Longest path between two nodes which passes through the root.)
Now the diam­e­ter of left and right subtree’s can be solved recur­sively. And Longest path between two nodes which passes through the root can be cal­cu­lated as 1 + height of left sub­tree + height of right subtree.