1506. Find Root of N-Ary Tree - Solution

The problem

You are given all the nodes of an N-ary tree as an array of Node objects, where each node has a unique value.

Return the root of the N-ary tree.

Custom testing:

An N-ary tree can be serialized as represented in its level order traversal where each group of children is separated by the null value (see examples).

For example, the above tree is serialized as [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].

The testing will be done in the following way:

The input data should be provided as a serialization of the tree.
The driver code will construct the tree from the serialized input data and put each Node object into an array in an arbitrary order.
The driver code will pass the array to findRoot, and your function should find and return the root Node object in the array.
The driver code will take the returned Node object and serialize it. If the serialized value and the input data are the same, the test passes.

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 * 10⁴].
Each node has a unique value.

Follow up:

Could you solve this problem in constant space complexity with a linear time algorithm?

Approach overview

Problem Overview: You receive a list of nodes representing an N-ary tree. Each node contains its value and references to its children, but the root node is not explicitly given. Your task is to determine which node is the root.

The key observation: every node appears exactly once as a child except the root. The root is the only node that never appears in any child list.

Approach 1: Hash Set of Children (O(n) time, O(n) space)

Traverse every node and add each child node to a hash set. After collecting all children, iterate through the original list of nodes. The node that never appears in the set must be the root. The logic works because every non-root node appears exactly once as a child somewhere in the tree.

This approach uses a simple membership lookup with hash tables. Insert and lookup operations are O(1) on average, making the overall solution linear. The tradeoff is extra memory proportional to the number of nodes.

Approach 2: Value Sum / Bit Manipulation Trick (O(n) time, O(1) space)

Instead of storing children, accumulate the sum of all node values and subtract the values of all child nodes. Since every node except the root appears exactly once as a child, all non-root values cancel out. The remaining value corresponds to the root node.

A similar trick uses XOR instead of addition, which avoids overflow and fits naturally with bit manipulation. XOR all node values, then XOR all child values. Identical values cancel out, leaving the root's value. Finally, scan the node list to return the node with that value. This approach runs in linear time with constant extra memory.

Approach 3: Parent Tracking with DFS Insight (O(n) time, O(n) space)

Another way is to explicitly record parent relationships. Traverse every node and mark each child as having a parent. After processing the entire list, the node without a recorded parent is the root. This method mirrors how you'd discover roots during a Depth-First Search traversal when building a tree from edges.

The idea is conceptually simple but uses extra space similar to the hash set approach. It is useful when working with general graph-style inputs where parent relationships must be tracked.

Recommended for interviews: The hash set approach is the most straightforward and communicates the key observation clearly. The XOR/sum trick shows deeper insight and achieves O(1) extra space, which often impresses interviewers. Start with the set-based explanation to demonstrate understanding of the tree structure, then mention the bit manipulation optimization.

Solution

Python

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


class Solution:
    def findRoot(self, tree: List['Node']) -> 'Node':
        x = 0
        for node in tree:
            x ^= node.val
            for child in node.children:
                x ^= child.val
        return next(node for node in tree if node.val == x)

Java

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;


    public Node() {
        children = new ArrayList<Node>();
    }

    public Node(int _val) {
        val = _val;
        children = new ArrayList<Node>();
    }

    public Node(int _val,ArrayList<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public Node findRoot(List<Node> tree) {
        int x = 0;
        for (Node node : tree) {
            x ^= node.val;
            for (Node child : node.children) {
                x ^= child.val;
            }
        }
        for (int i = 0;; ++i) {
            if (tree.get(i).val == x) {
                return tree.get(i);
            }
        }
    }
}

C++

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    Node* findRoot(vector<Node*> tree) {
        int x = 0;
        for (Node* node : tree) {
            x ^= node->val;
            for (Node* child : node->children) {
                x ^= child->val;
            }
        }
        for (int i = 0;; ++i) {
            if (tree[i]->val == x) {
                return tree[i];
            }
        }
    }
};

TypeScript

/**
 * Definition for Node.
 * class Node {
 *     val: number
 *     children: Node[]
 *     constructor(val?: number, children?: Node[]) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.children = (children===undefined ? [] : children)
 *     }
 * }
 */

function findRoot(tree: Node[]): Node | null {
    let x = 0;
    for (const node of tree) {
        x ^= node.val;
        for (const child of node.children) {
            x ^= child.val;
        }
    }
    return tree.find(node => node.val === x) || null;
}

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func findRoot(tree []*Node) *Node {
	x := 0
	for _, node := range tree {
		x ^= node.Val
		for _, child := range node.Children {
			x ^= child.Val
		}
	}
	for i := 0; ; i++ {
		if tree[i].Val == x {
			return tree[i]
		}
	}
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Hash Set of Children	O(n)	O(n)	Most intuitive solution; good when clarity is preferred over memory optimization
Value Sum / XOR Trick	O(n)	O(1)	Best when minimizing extra space; common interview optimization
Parent Tracking	O(n)	O(n)	Useful when explicitly building parent relationships or validating tree structure

Frequently asked questions

Is Find Root of N-Ary Tree easy or hard?

Find Root of N-Ary Tree is typically rated Medium difficulty. The implementation is simple once you recognize the core property that the root never appears as a child, but spotting the XOR or sum optimization requires deeper insight.

Find Root of N-Ary Tree Python/Java solution

In Python or Java, iterate through all nodes, add each child to a set, then return the node whose reference is not present in that set. The implementation is short and runs in O(n) time. The same logic works in C++, Go, and TypeScript with minor syntax differences.

How to solve Find Root of N-Ary Tree in O(n)?

Iterate through the node list and track all children using a hash set or XOR trick. Every non-root node appears exactly once as a child, while the root never appears as a child. After processing the list, the node missing from the child set—or the remaining XOR value—identifies the root in linear time.

What is the best approach for Find Root of N-Ary Tree?

The most common approach uses a hash set to store all child nodes. After scanning every node and its children, the node that never appears in the set is the root. This solution runs in O(n) time with O(n) extra space and clearly reflects the property that only the root has no parent.

Is Find Root of N-Ary Tree asked at Google/Amazon/Meta?

Tree structure problems and parent-child relationship detection frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of tree properties, hashing techniques, and constant-space tricks such as XOR cancellation.

What data structure is used in Find Root of N-Ary Tree?

Common solutions rely on a hash set to track child nodes or bit manipulation using XOR to cancel repeated values. The underlying structure being analyzed is an N-ary tree, where each node can have multiple children.

What is the time complexity of Find Root of N-Ary Tree?

The optimal solutions run in O(n) time where n is the number of nodes. Each node and each child reference is processed once while building a set, computing sums, or applying XOR operations. Space complexity ranges from O(1) for the XOR trick to O(n) when using a hash set.

Find Root of N-Ary Tree solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Find Root of N-Ary Tree solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems