Katkat
Back

Find the Root of the Largest Tree in a Child-to-Parent Forest

Goldman SachsSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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 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

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

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

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

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.