LeetCode 1506 - Find Root of N-Ary Tree

Difficulty: 🟡 Medium
Topics: Hash Table, Bit Manipulation, Tree, Depth-First Search

Solution

Problem Understanding

This problem gives us every node of an N-ary tree in an arbitrary order, and asks us to determine which node is the root of the tree.

An N-ary tree is a tree where each node can have zero or more children. Each node contains a unique integer value and a list of child nodes. The important detail is that the input is not given as a traditional tree structure starting from the root. Instead, we only receive an array containing all node objects in random order.

The task is to identify and return the one node that is the root.

The structure of the tree itself is already fully connected through the children references. The only missing information is which node should be considered the entry point of the tree.

The constraints are important:

There can be up to 5 * 10^4 nodes.
Every node value is unique.
The input always forms a valid tree.

These constraints immediately rule out inefficient repeated traversals. A quadratic solution could become too slow for large inputs.

The key property of a tree helps simplify the problem:

Every node except the root appears exactly once as a child of another node.
The root never appears as anyone's child.

That observation is the foundation of the optimal solutions.

Several edge cases are important:

A tree containing only one node. In this case, that node is both the root and the only node.
Nodes arriving in completely random order. We cannot assume the first node is the root.
Deep or wide trees. The algorithm must work regardless of shape.
Nodes with empty children lists. Leaf nodes should still be processed correctly.

The problem guarantees uniqueness of node values and validity of the tree, so we do not need to handle malformed input or duplicate values.

Approaches

Brute Force Approach

A straightforward solution is to check every node and determine whether it ever appears as a child of another node.

We can iterate through all nodes in the array. For each candidate node, we scan every other node's children list to see whether the candidate appears as a child. If it never appears as a child, then it must be the root.

This works because, in a tree, every non-root node has exactly one parent. Therefore, every non-root node appears somewhere inside another node's children list.

The brute force algorithm is correct, but inefficient. Suppose there are n nodes and each node may contain many children. Repeatedly scanning the entire structure for every candidate can lead to quadratic time complexity.

With up to 50,000 nodes, this approach becomes too slow.

Optimal Approach

The key observation is that every non-root node appears exactly once as a child, while the root never appears as a child.

Instead of repeatedly searching, we can process the tree once and record all child nodes in a hash set.

The algorithm becomes:

Add every child node into a set.
Iterate through all nodes again.
The node not found in the child set is the root.

This transforms the problem into a simple membership lookup problem.

There is also a follow-up asking for constant extra space. A clever mathematical observation helps here:

Sum all node values.
Subtract every child value.
The remaining value must be the root value.

Because every non-root value is added once and subtracted once, only the root remains.

However, since we still need to map the remaining value back to the corresponding node object, we perform one final scan through the nodes.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Repeatedly searches for parent relationships
Optimal Hash Set	O(n)	O(n)	Stores all child nodes for fast lookup
Optimal XOR/Sum Variant	O(n)	O(1)	Uses arithmetic cancellation property

Algorithm Walkthrough

The hash set approach is the clearest and most commonly accepted solution.

Create an empty hash set called children_set.

This set will contain every node that appears as a child somewhere in the tree. 2. Traverse every node in the input array.

For each node, iterate through its children list. 3. Add each child node into children_set.

Since every non-root node has exactly one parent, all non-root nodes will eventually appear in this set. 4. Traverse the input array again.

For each node, check whether it exists in children_set. 5. Return the first node not found in the set.

This node never appeared as a child, so it must be the root. 6. If no node is found, return None.

This case should never happen because the problem guarantees a valid tree.

Why it works

The correctness relies on a fundamental tree property:

Every node except the root has exactly one parent.
Therefore, every non-root node appears in some parent's children list.
The root has no parent, so it never appears as a child.

By collecting all child nodes, we effectively isolate every non-root node. The only remaining node outside the set is the root.

Python Solution

from typing import List, Optional

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

class Solution:
    def findRoot(self, tree: List['Node']) -> 'Node':
        children_set = set()

        # Collect all child nodes
        for node in tree:
            for child in node.children:
                children_set.add(child)

        # The node that never appears as a child is the root
        for node in tree:
            if node not in children_set:
                return node

        return None

The implementation follows the algorithm directly.

First, we create a hash set called children_set. This set stores references to every node that appears as a child somewhere in the tree.

Next, we iterate through every node in the input array. For each node, we traverse its children list and insert each child node into the set.

After this preprocessing phase, every non-root node is guaranteed to exist inside the set.

We then perform a second pass through the original node list. The first node not present in children_set is returned as the root.

The final return None is technically unnecessary for valid inputs, but it keeps the function syntactically complete.

Go Solution

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

func findRoot(tree []*Node) *Node {
    childrenSet := make(map[*Node]bool)

    // Collect all child nodes
    for _, node := range tree {
        for _, child := range node.Children {
            childrenSet[child] = true
        }
    }

    // Find the node that never appears as a child
    for _, node := range tree {
        if !childrenSet[node] {
            return node
        }
    }

    return nil
}

The Go implementation is structurally identical to the Python version.

Instead of Python's built-in set, Go uses a map[*Node]bool to simulate set behavior.

Node references are used as map keys, which works naturally because pointer identity uniquely identifies each node object.

The function returns nil if no root is found, although valid problem constraints guarantee that a root always exists.

Worked Examples

Example 1

Input:

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

Tree structure:

Suppose the input array order is:

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

Step 1: Build the child set

Current Node	Children Added	Child Set
5	none	{}
4	none	{}
3	5, 6	{5, 6}
6	none	{5, 6}
2	none	{5, 6}
1	3, 2, 4	{2, 3, 4, 5, 6}

Step 2: Find node not in child set

Node	In Child Set?
5	Yes
4	Yes
3	Yes
6	Yes
2	Yes
1	No

Therefore, 1 is the root.

Example 2

Input:

[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 tree is much larger, but the same logic applies.

Step 1: Add all child nodes

As we traverse the tree:

2, 3, 4, 5 become children
6, 7 become children
8 becomes a child
9, 10 become children
11, 12, 13 become children
14 becomes a child

Eventually, every node except 1 appears in the child set.

Step 2: Find missing node

When scanning the original node list:

Every node except 1 exists in the child set.
1 does not exist in the set.

Therefore, 1 is the root.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node and child relationship is processed once
Space	O(n)	The child set may contain all non-root nodes

The algorithm is linear because each node is visited a constant number of times. Every edge in the tree is processed once while building the child set.

The auxiliary space comes from storing all child nodes in the hash set. In the worst case, the set contains n - 1 nodes.

The follow-up constant space solution can reduce auxiliary space to O(1) by using arithmetic cancellation, but the hash set version is simpler and more intuitive.

Test Cases

# Definition for testing
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):
        children_set = set()

        for node in tree:
            for child in node.children:
                children_set.add(child)

        for node in tree:
            if node not in children_set:
                return node

        return None

sol = Solution()

# Test 1: Single node tree
node1 = Node(1)
assert sol.findRoot([node1]) == node1  # only node is the root

# Test 2: Simple N-ary tree
node5 = Node(5)
node6 = Node(6)
node3 = Node(3, [node5, node6])
node2 = Node(2)
node4 = Node(4)
node1 = Node(1, [node3, node2, node4])

tree = [node5, node4, node3, node6, node2, node1]
assert sol.findRoot(tree) == node1  # root found despite random order

# Test 3: Deep chain
node4 = Node(4)
node3 = Node(3, [node4])
node2 = Node(2, [node3])
node1 = Node(1, [node2])

tree = [node3, node1, node4, node2]
assert sol.findRoot(tree) == node1  # handles deep tree

# Test 4: Wide tree
children = [Node(i) for i in range(2, 11)]
root = Node(1, children)

tree = children + [root]
assert sol.findRoot(tree) == root  # handles many children

# Test 5: Larger irregular tree
node14 = Node(14)
node11 = Node(11, [node14])
node7 = Node(7, [node11])
node3 = Node(3, [node6 := Node(6), node7])
node8 = Node(8, [Node(12)])
node4 = Node(4, [node8])
node10 = Node(10)
node5 = Node(5, [Node(13)])
node9 = Node(9)
node2 = Node(2)
node1 = Node(1, [node2, node3, node4, node5])

tree = [
    node14, node11, node7, node3,
    node8, node4, node10, node5,
    node9, node2, node1
]

assert sol.findRoot(tree) == node1  # complex structure

Test Case Summary

Test	Why
Single node tree	Verifies smallest valid input
Simple N-ary tree	Confirms standard behavior
Deep chain	Tests skewed tree structure
Wide tree	Tests many children under one root
Larger irregular tree	Validates correctness on complex shapes

Edge Cases

Single Node Tree

A tree with only one node is the smallest valid input. Since the node has no parent and no children, the child set remains empty. During the second pass, the node is not found in the set and is correctly returned as the root.

A buggy implementation might incorrectly assume at least one parent-child relationship exists.

Arbitrary Input Order

The input array is explicitly stated to be in arbitrary order. The root may appear at the beginning, middle, or end of the array.

A naive solution that assumes the first node is the root would fail immediately. The implemented algorithm avoids this issue entirely because it determines the root based solely on structural relationships.

Deep or Highly Unbalanced Trees

Some trees may resemble linked lists, where each node has exactly one child. Recursive approaches could risk stack overflow in some languages if implemented carelessly.

The hash set solution is purely iterative and processes nodes uniformly regardless of tree shape, so it handles deep trees safely.

Nodes with Empty Children Lists

Leaf nodes contain empty children lists. The implementation naturally handles this because iterating over an empty list simply performs no operations.

No special-case logic is required for leaves.