1. O(n) Space

Intuition

The root of a tree is the only node that is never a child of any other node. By collecting all child nodes into a set, we can identify the root as the node whose value does not appear in the set. Every non-root node will appear exactly once as someone's child, but the root never will.

Algorithm

1. Create a set to store all child node values.
2. Iterate through every node in the tree and add all of its children's values to the set.
3. Iterate through the tree again and find the node whose value is not in the seen set.
4. Return that node as the root.

class Solution:
    def findRoot(self, tree: List['Node']) -> 'Node':
        # set that contains all the child nodes.
        seen = set()

        # add all the child nodes into the set
        for node in tree:
            for child in node.children:
                # we could either add the value or the node itself.
                seen.add(child.val)

        # find the node that is not in the child node set.
        for node in tree:
            if node.val not in seen:
                return node

Time & Space Complexity

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

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

---

2. O(1) Space

Intuition

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.

Algorithm

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.

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

Time & Space 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.