Find Root of N-Ary Tree

Find Root of N-Ary Tree

What is this problem about?

The Find Root of N-Ary Tree interview question asks you to identify the root of a tree given all its nodes in a shuffled list. Each node has a value and a list of children. The root is the unique node that is not a child of any other node. This Find Root of N-Ary Tree coding problem usually includes a constraint to solve it in $O(1)$ extra space.

Why is this asked in interviews?

Companies like Meta and Google use this to test your understanding of tree properties and your ability to optimize space. It evaluates if you can find a mathematical invariant (like a sum or XOR) that distinguishes the root from all other nodes. It’s a classic Bit Manipulation interview pattern or Math interview pattern task.

Algorithmic pattern used

This problem is best solved using XOR Summation or Value Summation.

1. The Invariant: Every node in the tree appears as a child exactly once, except for the root. Therefore, every node's value (or memory address) appears twice in the total set of (node + all children), while the root's value appears only once.
2. Logic:
   • Initialize rootXor = 0.
   • Iterate through every node in the list.
   • XOR rootXor with the node's value.
   • For every child of that node, XOR rootXor with the child's value.
3. Result: After processing all nodes and children, rootXor will equal the value of the root node.

Example explanation

Tree: 1 is root, children 2 and 3.

• Nodes given: {node(1), node(2), node(3)} in any order.
• Process node 1: xorSum ^ 1. Children {2, 3}: xorSum ^ 2 ^ 3.
• Process node 2: xorSum ^ 2. Children {}: no change.
• Process node 3: xorSum ^ 3. Children {}: no change. Total XOR: 1 ^ 2 ^ 3 ^ 2 ^ 3 = 1. The root value is 1.

Common mistakes candidates make

• Using a Set: Using $O(N)$ extra space to track which nodes have been seen as children. While correct, it misses the $O(1)$ space optimization.
• In-degree Count: Building an adjacency list to count in-degrees, which is also $O(N)$ space.
• Memory Addresses: Forgetting that if node values aren't unique, you must XOR the actual memory addresses (or unique IDs) of the node objects.

Interview preparation tip

Whenever a problem involves finding a "unique" element in a set where everything else appears an even number of times, think XOR. It’s the most efficient way to isolate a single outlier.