Code Implementation

# Definition for a Node.
class Node:
    def __init__(self, val, children=None):
        self.val = val
        self.children = children if children is not None else []

class Solution:
    def findRoot(self, tree: list) -> 'Node':
        # Use sum of all node values minus sum of all child node values
        # The difference will be the root's value
        total = 0
        for node in tree:
            total += node.val
            for child in node.children:
                total -= child.val
        # Now, find the node with value == total
        for node in tree:
            if node.val == total:
                return node
        return None
      

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    Node* findRoot(vector<Node*> tree) {
        int total = 0;
        for (Node* node : tree) {
            total += node->val;
            for (Node* child : node->children) {
                total -= child->val;
            }
        }
        for (Node* node : tree) {
            if (node->val == total) return node;
        }
        return nullptr;
    }
};
      

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public Node findRoot(List<Node> tree) {
        int total = 0;
        for (Node node : tree) {
            total += node.val;
            for (Node child : node.children) {
                total -= child.val;
            }
        }
        for (Node node : tree) {
            if (node.val == total) {
                return node;
            }
        }
        return null;
    }
}
      

/**
 * // Definition for a Node.
 * function Node(val, children) {
 *    this.val = val;
 *    this.children = children || [];
 * };
 */
/**
 * @param {Node[]} tree
 * @return {Node}
 */
var findRoot = function(tree) {
    let total = 0;
    for (let node of tree) {
        total += node.val;
        for (let child of node.children) {
            total -= child.val;
        }
    }
    for (let node of tree) {
        if (node.val === total) {
            return node;
        }
    }
    return null;
};
      

Problem Description

Given all the nodes of an N-ary tree as an unordered list tree, find the root node. Each node is an instance of a class Node that has a val (unique integer value) and a list of children. The input list contains all nodes, but not in any specific order. There is exactly one root node. You must return a reference to the root node, not create a new one. You may not reuse or duplicate nodes.

• There is always one valid solution.
• No node is reused as a child in the tree.
• Each node value is unique.

Thought Process

The problem gives us every node in the tree, but not the tree itself—just the nodes and their children. Our task is to find the node that is the root, using only the references provided.

At first, one might think to build a parent map or traverse the tree, but since we don't know the root, traversal isn't possible. Instead, we need to deduce the root by analyzing relationships in the given data.

The key insight is that every node except the root appears as a child of some other node. Only the root never appears as anyone's child. If we can identify which node is never listed as a child, that's the root.

Naively, we could create a set of all children and then look for the node not in that set. But we can optimize further using properties of node values or references.

Solution Approach

• Step 1: Sum of Node Values. Since each node value is unique and every node except the root appears as a child, if we sum all node values and subtract the sum of all child node values, the difference will be the value of the root node.
• Step 2: Find the Root Node. After computing the root value, we iterate through the original list and return the node whose value matches the result. This guarantees we return the exact node instance from the input.
• Why This Works: Every node's value is added once, and every child node's value is subtracted once. Only the root's value is not subtracted, so it remains.
• Alternative Approach: You could also use a set to track all nodes and then remove those that appear as children, but the sum approach is more space-efficient and elegant.

Example Walkthrough

Suppose the tree is:

• Node 1: children = [Node 2, Node 3]
• Node 2: children = []
• Node 3: children = [Node 4]
• Node 4: children = []

Step 1: Sum all node values. 1 + 2 + 3 + 4 = 10

Step 2: Subtract all child node values. Node 1's children: 2, 3; Node 3's child: 4. So: 2 + 3 + 4 = 9

Step 3: Compute root value. 10 - 9 = 1

Step 4: Find node with value 1 in the list and return it.

The root is Node 1, as expected.

Time and Space Complexity

• Brute-force Approach: Track all nodes and all children in sets. This requires O(n) time and O(n) space for the sets.
• Optimized (Sum) Approach: We iterate through the list twice: once to sum and subtract values, once to find the node. Each iteration is O(n), where n is the number of nodes. No extra space is required except a few variables, so space complexity is O(1).
• Big-O: Time complexity is O(n), space complexity is O(1).

Summary

The task is to find the root of an N-ary tree given all its nodes in no order. By leveraging the fact that every node except the root appears as a child, we can subtract all child node values from the sum of all node values to deduce the root's value. This method is both efficient and elegant, requiring only simple arithmetic and no extra data structures. The solution is O(n) time and O(1) space, and returns the exact node instance from the original list.