Root of the Largest Tree
Reported by candidates from Goldman Sachs's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Goldman Sachs reported this one in October 2026, and it looks friendlier than it is. Two parallel arrays, a forest, and you return the root of the biggest tree. The tree pattern is obvious, but the edge case is what bites: tie-breaking on the smallest root ID, and IDs that go negative or hit 10^9. If you're taking this OA in the next day or two, know the shape before you start typing. StealthCoder sits invisibly on your screen as a safety net if you blank mid-assessment, but the plan below is short enough to carry in your head.
The problem
You are given parallel integer arrays parents and children describing a forest of rooted trees. For every index i, parents[i] is the direct parent of children[i].
The nodes are exactly the distinct IDs that appear in either array. The associations form a valid acyclic forest, and every child appears at most once. A node that never appears in children is the root of its tree.
The size of a tree is its number of distinct nodes. Return the root ID of a tree with maximum size. If several trees have the same maximum size, return the smallest root ID.
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.
Constraints
1 <= parents.length = children.length <= 100000.
-10^9 <= parents[i], children[i] <= 10^9.
The associations form a valid acyclic forest.
Every child ID appears at most once, and parents[i] != children[i].Reported by candidates. Source: FastPrep
Pattern and pitfall
Build an adjacency map from parent to list of children. Collect every distinct ID into a set, and put every child ID into a second set. Roots are nodes in the first set but not the second. For each root, count its tree size with an iterative DFS or BFS. Track the best size, and on a tie keep the smaller root ID. The pitfall is recursion. With up to 100000 edges, a chain can be 100000 deep and a recursive DFS will overflow the stack in many languages, so use an explicit stack. Second pitfall: using array indexes as IDs. IDs range from -10^9 to 10^9, so use hash maps. Third: a tie-break written as strictly greater only, which returns the first root found, not the smallest. Total work is O(n). If you freeze live, StealthCoder is the hedge, but this is a map, a set difference, and one traversal.
If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.
You can drill Root of the Largest Tree cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Goldman Sachs's OA.
Goldman Sachs reuses patterns across OAs. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Root of the Largest Tree FAQ
How hard is Root of the Largest Tree really?+
Easy to medium. The logic is a graph traversal you've seen before. The difficulty is in the details: huge ID range, deep chains, and the smallest-root tie-break. If you handle those three, it's a quick solve.
What's the trick to finding the roots?+
A root is any ID that appears in parents but never in children. Put all children into a set, then scan the parents and keep the IDs not in that set. Since each child appears at most once, every tree has exactly one root.
Why not just recurse?+
A single tree can be a chain of 100000 nodes, which overflows the call stack in many languages. Use an explicit stack or a queue for the traversal. It's the same O(n) work with no depth risk.
How do I handle ties on tree size?+
Compare size first. If the size equals your current best, keep the smaller root ID. Write it as one condition: size greater, or size equal and root smaller. Test with a case where two trees have equal size.
How do I prepare for this in 48 hours?+
Practice building a hash map adjacency list and running an iterative DFS on a forest. Then write this exact problem once with negative IDs and a tie case. Check your tie-break and your handling of a single-edge input before submitting.