Largest Tree Root
MediumTrees ยท Goldman Sachs
A forest is described by links, where each [child, parent] pair says parent is the direct parent of child. Every node appears in at least one pair, and a node that is only ever a parent is a root.
Return the root of the tree with the most nodes. If several trees have the most nodes, return the smallest such root. If links is empty, return -1.
Example 1
- Input:
- links = [[2, 1], [3, 1], [5, 4], [6, 5], [7, 5]]
- Output:
- 4
- Explanation
- The tree rooted at 1 has 3 nodes and the tree rooted at 4 has 4 nodes.
Example 2
- Input:
- links = [[3, 9], [4, 9], [2, 7], [8, 7]]
- Output:
- 7
- Explanation
- Both trees have 3 nodes, so the smaller root wins.
Example 3
- Input:
- links = []
- Output:
- -1
Constraints
0 <= links.length <= 25001 <= child, parent <= 10^9- Each node appears as
childat most once, and the links contain no cycles.