We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Root of N-Ary Tree

Number: 1650

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given an array of Node objects representing all the nodes of an N-ary tree (with each node having a unique value), return the root node of the tree. The nodes are provided in an arbitrary order, and only the root node is not referenced as a child by any other node.

Key Insights

  • Every node except the root appears as a child of another node.
  • By summing all node values and then subtracting the sum of all children node values, the remaining value corresponds to the root.
  • This subtraction trick allows us to identify the root in a single pass of the data structure without extra memory for tracking child nodes.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes, since we iterate through all nodes and their children. Space Complexity: O(1) extra space using arithmetic accumulators.

Solution

The solution calculates two sums: one for all nodes' values and one for all children nodes' values. The difference between these gives the value of the root node since every node's value (except the root's) is added once as a child. Finally, we iterate over the nodes to find the node with the computed root value and return it. This approach meets the requirement of constant space complexity and linear time.

Code Solutions

# Python implementation with detailed comments
def findRoot(tree):
    # Initialize variables to store the sum of all node values and children values
    total_sum = 0
    children_sum = 0

    # Iterate over each node in the tree array
    for node in tree:
        total_sum += node.val  # Add current node's value to total_sum
        # Iterate over each child of the current node and add their values to children_sum
        for child in node.children:
            children_sum += child.val

    # The root's value is the difference between total_sum and children_sum
    root_val = total_sum - children_sum

    # Find and return the node with the value equal to root_val
    for node in tree:
        if node.val == root_val:
            return node
    return None  # This should never happen if the input tree is valid
← Back to All Questions