Loading...
Loading...
Loading...
In a big joint family tree, a step is one parent-child link. Rohan wants to know which two relatives are the furthest apart: the most steps along the tree from one to the other, never using a link twice.
Print that largest number of steps. This is the diameter of the tree. The path may or may not pass through the top person.
N for no node. Children are listed only for real nodes, and N tokens at the end of the line may be left out. For example, 1 2 3 N 4 is root 1 with children 2 and 3, and 4 is the right child of 2. The tree has at least one node.Example 1
Input
1 2 3 4 5
Output
3
The path 4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3) has 3 steps.
Example 2
Input
1 2 N 3 4 5 N N 6
Output
4
The longest path is 5 → 3 → 2 → 4 → 6, with 4 steps. It does not touch the root 1.
Try the problem first. Open one hint at a time.
Every path has one highest node. At that node the path goes down into the left side and into the right side.
The longest path that has node x as its highest node is height(left of x) + height(right of x) steps, with heights counted in nodes.
Compute the height of every node once, bottom-up, and update the best answer at every node, not only at the root.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor