Taro Logo

Find Root of N-Ary Tree

Medium
Google logo
Google
1 view
Topics:
Trees

You are given all the nodes of an N-ary tree. However, you are not given the root. Each node contains a unique value, and each node has a list of children. Your task is to find the root node of the N-ary tree.

For example, consider the following N-ary tree:

      1
     / | \
    2  3  4
   / \
  5   6

Assume you are given a list of Node objects, where each Node object has a val attribute representing its value and a children attribute representing a list of its child Node objects.

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

Your function should take a list of Node objects representing the nodes of the N-ary tree and return the root Node object. In the example above, the input would be a list of Node objects representing nodes with values 1, 2, 3, 4, 5, and 6. The function should return the Node object with value 1, as it is the root of the tree.

What is the most efficient way to find the root node, considering that the number of nodes (N) could be very large?

Solution


Naive Solution

The naive approach to finding the root of an N-ary tree, given a list of all nodes, is to iterate through each node and check if it's a child of any other node. The node that is not a child of any other node is the root.

Code

def find_root_naive(nodes):
    children = set()
    for node in nodes:
        if node.children:
            for child in node.children:
                children.add(child)
    
    for node in nodes:
        if node not in children:
            return node
    return None

Time Complexity

O(N*M), where N is the number of nodes, and M is the average number of children per node. We iterate through all the nodes, and for each node, we iterate through its children to build a set of all children. Then we iterate through all nodes again to check if a node is present in the set of children.

Space Complexity

O(C), where C is the total number of children in the tree. This is the space used by the children set. In the worst-case scenario, where all nodes are children of some other node, the space complexity can be O(N).

Optimal Solution

The optimal solution uses the property that the sum of all node values, minus the sum of all nodes that are children, will leave you with the root node's value. This works because every non-root node appears once as a node itself and once as a child of another node, thus cancelling out its value. The root node, however, only appears once as a node itself and never as a child.

Edge Cases

  • Empty list of nodes: return None.
  • Only one node: that node is the root.
  • Duplicate values: this approach relies on node identity, not node value, so duplicate values do not affect the correctness.

Code

def find_root(nodes):
    if not nodes:
        return None

    total_sum = 0
    children_sum = 0

    for node in nodes:
        total_sum += node.val
        if node.children:
            for child in node.children:
                children_sum += child.val

    root_val = total_sum - children_sum

    for node in nodes:
        if node.val == root_val:
            return node
    return None

# Assuming a Node class like this:
# class Node:
#     def __init__(self, val):
#         self.val = val
#         self.children = []

Time Complexity

O(N), where N is the number of nodes. We iterate through the list of nodes once to calculate the total sum of the node values, and then we iterate through the nodes children to determine the sum of all children. We iterate one last time to find the node with the appropriate value. All operations are linear with respect to the number of nodes.

Space Complexity

O(1). We are only using a few integer variables to store sums, regardless of the number of nodes. The space used does not scale with the input size.