FastPrep
Problem · Graph

Root of the Largest Tree

Learn this problem
● MediumGoldman SachsPHONE SCREEN

Problem statement

You are given parent-to-child associations describing a forest of rooted trees. For every index i, parents[i] is the direct parent of children[i].

Every node belongs to exactly one tree, every non-root node has exactly one parent, and the forest contains no cycles. Exactly one tree has strictly more distinct nodes than every other tree.

Return the root node ID of that largest tree.

Function

findLargestTreeRoot(parents: int[], children: int[]) → int

Examples

Example 1

parents = [1,1,2,10]children = [2,3,4,11]return = 1

The tree rooted at 1 contains nodes {1,2,3,4}. The tree rooted at 10 contains {10,11}, so return 1.

Example 2

parents = [5,8,8,9]children = [6,9,10,11]return = 8

The tree rooted at 8 contains 8,9,10,11, while the other tree contains only 5,6.

More Goldman Sachs problems

drafts saved locally
public int findLargestTreeRoot(int[] parents, int[] children) {
  // write your code here
}
parents[1,1,2,10]
children[2,3,4,11]
expected1
checking account