Root of the largest tree in a forest

You are given a list relations. Each entry [child, parent] says that parent is the direct parent of child. Together the relations form a forest: there are no cycles, and every node has at most one parent. Node IDs are integers, and the forest contains only the nodes that appear in relations.

A root is a node that appears in relations but never as a child. The size of a tree is the number of distinct nodes in it, root included.

Implement:

def largest_tree_root(relations: list[list[int]]) -> int | None

The function returns the root of the tree with the largest size. If two or more trees have the same size, return the smallest root ID. If relations is empty, return None.

Constraints

• 0 <= len(relations) <= 10^5
• Node IDs are non-negative integers up to 10^9.
• A tree can be a single chain up to 10^5 nodes deep.

Example 1

relations = [[4, 9], [7, 9], [1, 7], [3, 2]]

The tree rooted at 9 holds {9, 4, 7, 1}, so its size is 4. The tree rooted at 2 holds {2, 3}, so its size is 2. Answer: 9.

Example 2

relations = [[15, 20], [16, 20], [31, 30], [32, 30]]

Both trees have 3 nodes, so the smaller root wins. Answer: 20.

Reconstructed from the reported question; details may differ from what interviewers ask.