> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Find Root of N-Ary Tree Python Solution

> Tested Python solution for LeetCode 1506 with 29 pytest cases. Generate a practice environment with lcpy.

LeetCode 1506, [Medium](/catalog/medium). Topics: [Bit Manipulation](/catalog/topics/bit-manipulation), [Tree](/catalog/topics/tree), [Depth-First Search](/catalog/topics/depth-first-search), [Hash Table](/catalog/topics/hash-table). [View on LeetCode](https://leetcode.com/problems/find-root-of-n-ary-tree/description/).

Generate this problem as a practice environment: tested reference solution, 29 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1506   # by problem number
lcpy gen -s find_root_of_n_ary_tree   # by problem name
```

## 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).

![Example 1](https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png)

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:

1. The **input data** should be provided as a serialization of the tree.
2. The driver code will construct the tree from the serialized input data and put each `Node` object into an array **in an arbitrary order**.
3. The driver code will pass the array to `findRoot`, and your function should find and return the root `Node` object in the array.
4. 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**.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png)

```
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](https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png)

```
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^4]`.
* Each node has a **unique** value.

**Follow up:** Could you solve this problem in constant space complexity with a linear time algorithm?

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_root_of_n_ary_tree/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_root_of_n_ary_tree/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from __future__ import annotations


class Node:
    def __init__(self, val: int = 0, children: list[Node] | None = None) -> None:
        self.val = val
        self.children = children if children is not None else []


class Solution:
    # Time: O(n)
    # Space: O(1)

    def find_root(self, tree: list[Node]) -> Node:
        # Every value appears once as a node and once more as a child if it is
        # not the root, so XOR-ing all node values with all child values leaves
        # exactly the root's value.
        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)
```

## Complexity

| Time | Space |
| - | - |
| O(n) | O(1) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.