Amazon Online Assessment (OA) - Highest Tenure

Imagine that an employment tree represents the formal employee hierarchy for a company.

Manager nodes have child nodes for each employee that reports to them; each of these employees can, in turn, have child nodes representing their respective reporters. Each node in the tree contains an integer representing the number of months the employee has spent at the company. Team tenure is computed as the average tenure of the manager and all the company employees working below the manager. The oldest team has the highest team tenure.

Write an algorithm to find the manager of the team with the highest tenure. An employee must have child nodes to be a manager.

Input

The input consists of an argument:

president: a node representing the root node of the employee hierarchy

Output

Return the node which has the oldest team.

Note

There will be at least one child node in the tree and there will be no ties.

Examples

Example 1:

Input:

Output: 18

Explanation:

There are three managers in this tree with the following team tenures:

12 => (11+2+3+12)/4 = 7

18 => (18+15+8)/3 = 13.67

20 => (12+11+2+3+18+15+8+20)/8 = 11.125

Try it yourself