112. Largest Tree in a Forest

Largest Tree in a Forest

Given a forest represented by a list of child-parent relationships, find the root of the tree that contains the maximum number of nodes.

Each relationship is provided as a single string in relations using the format:
child,parent

This means:

child is a direct child of parent
each node is identified by an integer ID
a child can have at most one immediate parent
a parent can have zero or more immediate children

The given relationships form a valid forest, meaning:

there may be one or more disconnected trees
there are no cycles
every non-root node appears as a child exactly once

Return the root ID of the tree with the largest number of nodes.

If multiple trees have the same maximum size, return the root with the higher ID.

Method Signature

int largestTreeRoot(List<String> relations)

Parameters

relations is a list of strings
each string is in the format child,parent
both child and parent are integer node IDs

Returns

the integer ID of the root of the largest tree in the forest

Important Details

A node that never appears as a child is a root.
The size of a tree is the total number of distinct nodes in that tree, including its root.
All node IDs are integers.
The input list may be in any order.
The same node ID should be counted only once within its tree.

Constraints

1 ≤ relations.size() ≤ 100000
-10^9 ≤ nodeId ≤ 10^9
Each entry in relations contains exactly one comma.
Each parsed relationship represents child != parent.
The input forms a valid forest.

Examples

Example 1

Method call: largestTreeRoot(relations = List.of("1,2", "3,4"))

Output: 4

Explanation: The forest has two trees:

Tree rooted at 2: nodes {2, 1}, size = 2
Tree rooted at 4: nodes {4, 3}, size = 2

Both trees have the same size, so the higher root ID is returned.

Example 2

Method call: largestTreeRoot(relations = List.of("1,4", "2,4", "3,5", "6,5", "7,6"))

Output: 5

Explanation: The forest has two trees:

Tree rooted at 4: nodes {4, 1, 2}, size = 3
Tree rooted at 5: nodes {5, 3, 6, 7}, size = 4

The tree rooted at 5 is larger.

Example 3

Method call: largestTreeRoot(relations = List.of("10,20", "30,20", "40,50", "60,50", "70,50"))

Output: 50

Explanation: The forest has two trees:

Tree rooted at 20: nodes {20, 10, 30}, size = 3
Tree rooted at 50: nodes {50, 40, 60, 70}, size = 4

The tree rooted at 50 has more nodes.

Example 4

Method call: largestTreeRoot(relations = List.of("2,8", "3,8", "4,9", "5,9"))

Output: 9

Explanation: The forest has two trees:

Tree rooted at 8: nodes {8, 2, 3}, size = 3
Tree rooted at 9: nodes {9, 4, 5}, size = 3

Since the sizes are equal, return the higher root ID, which is 9.