Find Root of N-Ary Tree

How it works

Every node except the root appears exactly once as a parent and exactly once as a child. If we add each node's value as a parent and subtract each child's value, all non-root nodes will cancel out (added once, subtracted once). The root is only added as a parent but never subtracted as a child, so the final sum equals the root's value.

Steps

1. Initialize valueSum = 0.
2. For each node in the tree:
   • Add the node's value to valueSum (counting it as a parent).
   • Subtract each child's value from valueSum (counting it as a child).
3. Find and return the node whose value equals valueSum.

Complexity

• Time complexity: O(N)
• Space complexity: O(1)

Where N is the length of the input list, which is also the number of nodes in the N-ary tree.

Things to watch for

Confusing Node Values with Node References

When building the set of child nodes, you can store either the node's value or the node reference itself. However, be consistent. If you store values, compare values when finding the root. If you store references, compare references. Mixing the two leads to incorrect results.

Assuming the Root is Always at Index 0

The input list contains nodes in arbitrary order, not level-order or any specific traversal order. Never assume the root appears first in the list. Always iterate through all nodes to identify which one is not a child of any other.

Integer Overflow in the Sum Approach

When using the O(1) space solution that adds parent values and subtracts child values, be aware of potential integer overflow for very large trees with large node values. In languages with fixed-size integers, the sum could overflow before the final cancellation produces the correct root value.

from typing import List

class Solution:
    def findRoot(self, tree: List['Node']) -> 'Node':
        value_sum = 0

        for node in tree:
            # the value is added as a parent node
            value_sum += node.val
            for child in node.children:
                # the value is deducted as a child node.
                value_sum -= child.val

        # the value of the root node is `value_sum`
        for node in tree:
            if node.val == value_sum:
                return node

class Solution {
public:
    Node* findRoot(vector<Node*> tree) {
        int value_sum = 0;

        for (Node* node : tree) {
            // the value is added as a parent node
            value_sum += node->val;
            for (Node* child : node->children) {
                // the value is deducted as a child node.
                value_sum -= child->val;
            }
        }

        // the value of the root node is `value_sum`
        for (Node* node : tree) {
            if (node->val == value_sum) {
                return node;
            }
        }
        return nullptr;
    }
};