Find Root of N-Ary Tree

Updated on 29 May, 2025
Find Root of N-Ary Tree header image

Problem Statement

In the given problem, you are entrusted with a seemingly straightforward but intriguing task: determining the root of an N-ary tree from an array of its nodes. Each node, represented as a Node object, carries a unique value which eliminates the possibility of duplicate values within the tree. The unique challenge presented here lies in identifying the root node without the explicit structure of the tree, since the nodes are provided in an arbitrary sequence.

To clarify the serialization method involved, the N-ary tree's structure is captured through a level order traversal, where breaks in continuity of child nodes are marked with the null value. This serialized form is crucial as it serves both as a means for reconstructing the tree in tests and validating the correctness of your function's output.

During tests, your function is expected to find and return the root node based on the provided unordered array of nodes. The system that tests this functionality will serialize the node returned by your function and match it against the originally provided serialized data to ascertain the accuracy of the solution.

Examples

Example 1

Input:

tree = [1,null,3,2,4,null,5,6]

Output:

[1,null,3,2,4,null,5,6]

Explanation:

The tree from the input data is shown above.
The driver code creates the tree and gives findRoot the Node objects in an arbitrary order.
For example, the passed array could be [Node(5),Node(4),Node(3),Node(6),Node(2),Node(1)] or [Node(2),Node(6),Node(1),Node(3),Node(5),Node(4)].
The findRoot function should return the root Node(1), and the driver code will serialize it and compare with the input data.
The input data and serialized Node(1) are the same, so the test passes.

Example 2

Input:

tree = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

Output:

[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

Constraints

  • The total number of nodes is between [1, 5 * 104].
  • Each node has a unique value.

Approach and Intuition

To work towards finding the root of the N-ary tree based on the given constraints and examples, consider the following steps informed by the intuition about tree structures and node relationships:

  1. Understand the Properties of Root Node:

    • The root node is the only node in the tree without any parent.
    • Every other node in the tree will have exactly one parent.
  2. Initial Thoughts on Implementation:

    • Given an array of nodes, each of which knows its children but not its parent, the challenge becomes identifying the node which is not listed as a child of any other node.
    • If you can demonstrate that a node does NOT appear as a child of any other node in the array, this node must be the root.
  3. Potential Approach:

    • Create a set or another suitable data structure to track all the child nodes seen as you iterate through the array of Node objects.
    • Iterate through each node's children and add them to this set.
    • Once all nodes have been processed, any node not in your "children set" is the root.
  4. Optimization Considerations:

    • Given the constraints of nodes (between 1 and 50,000), the approach to process each node in a single pass (O(n) complexity regarding the number of nodes) would be efficient.
    • Careful attention must be paid to the memory usage, especially the structure used to store child references. A balance between time complexity and spatial complexity is vital.

This approach, rooted in fundamental properties of trees, offers a straightforward solution to identifying the root node without reconstructing the entire tree, which ensures efficiency given the constraints on the number of nodes and their unique values.

Solutions

  • Java
  • Python
java
class Solution {
    public Node locateRootNode(List<Node> treeNodes) {

        Integer accumulatedValue = 0;

        for (Node node : treeNodes) {
            accumulatedValue += node.val;
            for (Node childNode : node.children)
                accumulatedValue -= childNode.val;
        }

        Node rootNode = null;
        for (Node node : treeNodes) {
            if (node.val == accumulatedValue) {
                rootNode = node;
                break;
            }
        }
        return rootNode;
    }
}

The Java solution provided aims to find the root node of an N-Ary tree where nodes are represented using instances of a Node class, which contains a list of child nodes. The method locateRootNode takes a list of all nodes in the tree as input.

  • Calculate a unique root identifier by traversing each node and updating the accumulatedValue. Here's what happens during this traversal:

    • Add the value of the node to accumulatedValue.
    • Subtract the values of all its children from accumulatedValue.

    This computation leverages the characteristic that the root node's value is not subtracted as a child in any node calculations. Thus, the remaining value of accumulatedValue after the complete traversal will be equal to the value of the root node.

  • Identify the root node by iterating through each node again and checking which node's value matches the remaining accumulatedValue.

  • Return the identified root node.

This method stands out due to its efficient use of a single value (accumulatedValue) to determine the root without needing additional data structures or complex computations. It operates in linear time complexity, O(n), where n is the number of nodes, since each node is processed individually in sequence.

python
"""
# Class structure for a Tree Node.
class TreeNode:
    def __init__(self, value=None, kids=None):
        self.value = value
        self.kids = kids if kids is not None else []
"""

class SolutionFinder:
    def locateRootNode(self, nodeList: List['TreeNode']) -> 'TreeNode':
        accumulated_value = 0

        for treeNode in nodeList:
            # Adding value from a potential root candidate
            accumulated_value += treeNode.value
            for kid in treeNode.kids:
                # Removing value from a non-root candidate
                accumulated_value -= kid.value

        # Identifying root node based on accumulated sum
        for treeNode in nodeList:
            if treeNode.value == accumulated_value:
                return treeNode

This solution identifies the root node of an N-ary tree given a list of all nodes. Each node in the tree is represented by an instance of the TreeNode class, which contains a value and a list of kids (child nodes).

  • The TreeNode class initialization sets the node's value and initializes its children. If no children are provided, it defaults to an empty list.
  • In the SolutionFinder class, the locateRootNode method calculates the root by leveraging the unique property that the root node's value will be the difference between the sum of all possible root values and the sum of values of non-root nodes:
    1. Initialize an accumulator.
    2. Iterate through each node in the given list, adding each node's value to the accumulator.
    3. For each child of these nodes, subtract the child's value from the accumulator.
    4. After processing all nodes, iterate again through the list to find a node whose value matches the accumulated result. This node is the root.

Using this method ensures that the root node is identified efficiently without the need to construct the tree explicitly or modify the tree structure. This approach takes advantage of arithmetic properties to determine the root in a straightforward manner.

Comments

No comments yet.