Find the Root of the Largest Tree in a Child-to-Parent Forest
Company: Goldman Sachs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a list of child-to-parent relationships that together describe a forest, that is, a collection of disjoint rooted trees. Each relationship `[child, parent]` states that node `child` has parent `parent`, and every node is identified by an integer ID.
Find the tree that contains the most nodes and return the ID of its root. If several trees share the largest size, return the smallest root ID among them.
### Function Signature
```python
def largest_tree_root(relations: list[list[int]]) -> int:
```
Each element of `relations` is a pair `[child, parent]`.
### Rules
- The nodes of the forest are exactly the IDs that appear in `relations`, as a child, as a parent, or as both.
- A root is a node that never appears as a child.
- The size of a tree is the number of nodes in it, counting the root.
- Trees are compared by size first. Among the trees with the largest size, the answer is the smallest root ID.
### Constraints
- `1 <= len(relations) <= 10^5`
- `0 <= child, parent <= 10^9` and `child != parent` for every relationship.
- Each ID appears as a child at most once, so every node has at most one parent and no relationship is repeated.
- The relationships contain no cycles, so every node leads up to exactly one root.
- The relationships are given in no particular order.
### Examples
**Example 1**
```text
Input: relations = [[1, 2], [3, 4], [5, 4], [6, 4], [2, 7]]
Output: 4
```
There are two trees. The tree rooted at `7` contains `7`, `2` and `1`, so its size is 3. The tree rooted at `4` contains `4`, `3`, `5` and `6`, so its size is 4. The larger tree's root is `4`.
**Example 2**
```text
Input: relations = [[2, 9], [5, 3]]
Output: 3
```
The tree rooted at `9` contains `9` and `2`, and the tree rooted at `3` contains `3` and `5`. Both have size 2, so the smaller root ID, `3`, is returned.
**Example 3**
```text
Input: relations = [[3, 1], [1, 100], [2, 100], [50, 60]]
Output: 100
```
The tree rooted at `100` contains `100`, `1`, `2` and `3`, so its size is 4. The tree rooted at `60` contains `60` and `50`, so its size is 2. Size is compared first, so the answer is `100` even though `60` is the smaller ID.
Overview: Given a list of child-to-parent pairs that form a forest of rooted trees, return the root ID of the tree with the most nodes, breaking size ties by the smallest root ID. Tests building a forest from an edge list, identifying roots, counting tree sizes, and applying a precise tie-break rule.
You are given `relations`, a list of child-to-parent pairs that together describe a forest, that is, a collection of disjoint rooted trees. Each pair `[child, parent]` states that node `child` has parent `parent`, and every node is identified by an integer ID.
Return the root ID of the tree that contains the most nodes. If several trees share the largest size, return the smallest root ID among them.
Rules:
- The nodes of the forest are exactly the IDs that appear in `relations`, as a child, as a parent, or as both.
- A root is a node that never appears as a child.
- The size of a tree is the number of nodes in it, counting the root.
- Trees are compared by size first. Among the trees with the largest size, the answer is the smallest root ID.
The function returns a single integer: the chosen root ID. No ID or tree size can exceed 2^31 - 1 (IDs are at most 10^9 and a tree has at most 10^5 + 1 nodes), so a 32-bit `int` is sufficient in Java and C++.
Example 1:
Input: relations = [[2, 9], [5, 3]]
Output: 3
The tree rooted at 9 contains 9 and 2, and the tree rooted at 3 contains 3 and 5. Both have size 2, so the smaller root ID, 3, is returned.
Example 2:
Input: relations = [[3, 1], [1, 100], [2, 100], [50, 60]]
Output: 100
The tree rooted at 100 contains 100, 1, 2 and 3, so its size is 4. The tree rooted at 60 contains 60 and 50, so its size is 2. Size is compared first, so the answer is 100 even though 60 is the smaller ID.
Constraints:
- 1 <= len(relations) <= 10^5
- 0 <= child, parent <= 10^9 and child != parent for every relationship.
- Each ID appears as a child at most once, so every node has at most one parent and no relationship is repeated.
- The relationships contain no cycles, so every node leads up to exactly one root.
- The relationships are given in no particular order.
Constraints
- 1 <= len(relations) <= 10^5
- 0 <= child, parent <= 10^9 and child != parent for every relationship.
- Each ID appears as a child at most once, so every node has at most one parent and no relationship is repeated.
- The relationships contain no cycles, so every node leads up to exactly one root.
- The relationships are given in no particular order.
Examples
Input: ([[3, 7]],)
Expected Output: 7
Explanation: Minimum valid: one relation forms a two-node tree whose root is the parent 7, not the smaller ID 3.
Input: ([[1, 2], [3, 4], [5, 4], [6, 4], [2, 7]],)
Expected Output: 4
Explanation: Source Example 1: root 7 has size 3 and root 4 has size 4.
Hints
- A root is any ID that appears somewhere in relations but never as a child, so the forest has exactly one tree per such ID.
- The pairs arrive in no particular order: the edge linking a node's parent to its own parent may appear anywhere in the list, so each node must be credited to the root at the top of its chain, not to its immediate parent.
- A tree's size counts every node in it, not just the root's direct children; chains can be about 10^5 nodes deep, and equal sizes are broken by the smaller root ID.