LeetCode 1506: Find Root of N-Ary Tree

Explanation:

To find the root of an N-ary tree, we can iterate through each node in the tree and keep track of the nodes that are pointed to by other nodes. The root node will be the one that is not pointed to by any other node.

Algorithm:

1. Initialize a HashMap to store each node along with the count of references to that node.
2. Iterate through each node in the tree.
3. For each child node of the current node, increment the count of references in the HashMap.
4. After iterating through all nodes, the node with a count of references equal to 0 is the root node.

Time Complexity: O(N), where N is the number of nodes in the tree. Space Complexity: O(N) for storing nodes in the HashMap. :

class Solution {
    public Node findRoot(List<Node> tree) {
        Map<Node, Integer> refCount = new HashMap<>();
        
        for (Node node : tree) {
            refCount.put(node, refCount.getOrDefault(node, 0));
            for (Node child : node.children) {
                refCount.put(child, refCount.getOrDefault(child, 0) + 1);
            }
        }
        
        for (Node node : tree) {
            if (refCount.get(node) == 0) {
                return node;
            }
        }
        
        return null;
    }
}