Find Root of N-Ary Tree - Solution & Explanation

Problem Overview: You receive a list of nodes representing an N-ary tree. Each node contains its value and references to its children, but the root node is not explicitly given. Your task is to determine which node is the root.

The key observation: every node appears exactly once as a child except the root. The root is the only node that never appears in any child list.

Approach 1: Hash Set of Children (O(n) time, O(n) space)

Traverse every node and add each child node to a hash set. After collecting all children, iterate through the original list of nodes. The node that never appears in the set must be the root. The logic works because every non-root node appears exactly once as a child somewhere in the tree.

This approach uses a simple membership lookup with hash tables. Insert and lookup operations are O(1) on average, making the overall solution linear. The tradeoff is extra memory proportional to the number of nodes.

Approach 2: Value Sum / Bit Manipulation Trick (O(n) time, O(1) space)

Instead of storing children, accumulate the sum of all node values and subtract the values of all child nodes. Since every node except the root appears exactly once as a child, all non-root values cancel out. The remaining value corresponds to the root node.

A similar trick uses XOR instead of addition, which avoids overflow and fits naturally with bit manipulation. XOR all node values, then XOR all child values. Identical values cancel out, leaving the root's value. Finally, scan the node list to return the node with that value. This approach runs in linear time with constant extra memory.

Approach 3: Parent Tracking with DFS Insight (O(n) time, O(n) space)

Another way is to explicitly record parent relationships. Traverse every node and mark each child as having a parent. After processing the entire list, the node without a recorded parent is the root. This method mirrors how you'd discover roots during a Depth-First Search traversal when building a tree from edges.

The idea is conceptually simple but uses extra space similar to the hash set approach. It is useful when working with general graph-style inputs where parent relationships must be tracked.

Recommended for interviews: The hash set approach is the most straightforward and communicates the key observation clearly. The XOR/sum trick shows deeper insight and achieves O(1) extra space, which often impresses interviewers. Start with the set-based explanation to demonstrate understanding of the tree structure, then mention the bit manipulation optimization.