Find Root Of N Ary Tree - Leetcode Solution

Problem Statement:

The problem requires finding the root node of an N-ary tree given only the list of nodes. Each node in the tree is represented by a Node class which contains a unique value indicating the node's identity, a list of children, and a flag indicating whether the node is the root of the tree or not.

Solution:

The solution to this problem requires identifying the root node of the tree, which is not given in the input. This can be done by starting with any node in the tree, and traversing to its parent node recursively until the root node is reached.

To implement this solution, we can create a HashMap (or dictionary) that maps each node's value to its corresponding Node object. We can then iterate over each node in the list and add it to the HashMap. Once all the nodes are added, we can start with any node in the tree and traverse to its parent recursively until we reach the root node.

The following is the implementation of the solution in Python:

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

class Solution(object):
    def findRoot(self, tree):
        """
        :type tree: List[Node]
        :rtype: Node
        """
        # create a HashMap that maps each node's value to its corresponding Node object
        nodes = {}
        for node in tree:
            nodes[node.val] = node
        
        # start with any node in the tree and traverse to its parent recursively until we reach the root node
        for node in nodes.values():
            if node.children:
                for child in node.children:
                    nodes[child.val].parent = node
            else:
                root = node
        
        while hasattr(root, 'parent'):
            root = root.parent
        
        return root

In the above solution, we create a Hashmap (or dictionary) that maps each node's value to its corresponding Node object. We then iterate over each node in the list and add it to the HashMap. Once all the nodes are added, we start with any node in the tree and traverse to its parent recursively until we reach the root node. If a node has children, we iterate over its children and set their parent attribute to the current node. Once we reach a node that has no parent, that node is the root node of the tree.

In the end, we return the root node of the tree. This solution has a time complexity of O(n) and a space complexity of O(n), where n is the number of nodes in the tree.

1