Week 2 Bonus - Find Root of N-Ary Tree
Tags: leetcode, python, challenge
Published: 2021-01-14 18:41:50

## The Problem

>You are given all the nodes of an [N-ary tree](https://leetcode.com/articles/introduction-to-n-ary-trees/) 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).

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/p63twrlwccwmsj8zj2xf.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__.

__Example 1:__

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/zvxuvxnn0pgtcc8s18vd.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:__

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/3kfqgnstuui3k3ekwmyn.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 * 104]`.
* Each node has a unique value.

__Follow up:__

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

## My Tests

I didn't write any tests for this one. 

## My Solution

```python
class Solution:
    def findRoot(self, tree: List['Node']) -> 'Node':        
        c = {}
        n = {}
        for node in tree:            
            n[node.val] = node
            if node.children is not None:
                for ch in node.children:                    
                    c[ch.val] = True
        for k in n:
            if k not in c:
                return n[k]
        return None
```

## Analysis

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/oeb3zzc49j5udz33dfgq.png)

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/5zh2ibvkv78tqv9b6bz3.png)

## My Commentary

I did this one in a couple of minutes and am being very lazy. I am certain my solution is not a great one. 

One fact we know about the root node of the tree is that it cannot be the child of another tree. Given that, we can store all the child nodes values in a hash map and all the nodes in a map. Then we can look up each node value in the child map. If one of them is not there then it must be the root. 

This seems like a really hacky solution to me but I've already done one challenge today and don't have the energy to improve this one. It doesn't perform too badly in the analysis at least.