Loading...
Loading...
Loading...
A software company in Pune keeps its reporting lines as a tree of employee IDs. Every ID is different. A person is in their own team, and also in the team of every manager above them.
Two employees, a and b, need one person to approve their joint project. Print the ID of the lowest person whose team contains both a and b. If a manages b, the answer is a.
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, and all values are different. The second line has two integers a and b, both IDs in the tree. They may be the same.Example 1
Input
3 5 1 6 2 0 8 N N 7 4 7 8
Output
3
7 is under 5 and 8 is under 1. Only the top person 3 has both in their team.
Example 2
Input
3 5 1 6 2 0 8 N N 7 4 5 4
Output
5
4 is under 2, which is under 5. So 5 is the answer: a person is in their own team.
Try the problem first. Open one hint at a time.
The values are IDs, not a sorted order. Comparing a and b with a manager's ID tells you nothing about where they are.
Ask each person: is a or b in my team? A method can return the node it found, or null when it found neither.
If a person is a or b, return that person. If the left side and the right side both found someone, this person is the answer.
Otherwise pass up whatever one side found.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor