Solution

Definition of Diameter: The diameter of the tree is the longest path between any two nodes. This path may or may not pass through the root. Hence, we need to compute the longest paths in the subtree of each node.

Method 1 - DFS

We can use a recursive function to traverse through child nodes and calculate the heights.

Here is the approach:

Start from the root and recursively calculate the heights of the subtrees of all child nodes.
The height of a node is defined as the longest path from the node to any leaf.
For each node, calculate the longest two heights among its children (let's call them h1 and h2).
The local diameter at a node will be h1 + h2.
Update the global diameter (ans) to be the maximum of the current global diameter and the local diameter.

pick any node u
find the node which is farthest from u, call it x (calculate using the same approach as in Solution 1)
find the node which is farthest from x, call it q (calculate using the same approach as in Solution 1)

The answer will be the length of a path from x to q.

Code

Related Tags