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?
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.
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
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.
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).
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.
None
.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 = []
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.
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.