Find the Root of N-ary Tree (Graph Traversal)

To solve finding the root of an N-ary tree, I would first clarify the input format. Assuming we have a list of nodes where each contains an ID and a list of child IDs, my goal is to identify the node that never appears as a child. A brute-force approach comparing every node against every other node's children would take O(N^2) time, which is inefficient for large datasets common at Google. Instead, I propose an O(N) time and O(N) space solution using a Hash Set. The core insight is that the root is the unique element present in the node list but absent from the aggregate list of all children. First, I iterate through the entire input array. For each node, I add its ID to a 'seenChildren' set. Simultaneously, I maintain a set of all node IDs encountered. After processing all nodes, I iterate through the 'allNodes' set and check which ID does not exist in 'seenChildren'. That missing ID is our root. For example, if we have nodes [A, B, C] where A has children [B, C], and B and C are leaves, B and C go into the seenChildren set. When we check A, it is not in that set, identifying it as the root. This approach handles N-ary structures naturally without recursion depth issues. It is robust, scalable, and demonstrates the ability to leverage data structures for optimization rather than relying on nested loops.