---
tags: leetcode
---

# [1506. Find Root of N-Ary Tree](https://leetcode.com/problems/find-root-of-n-ary-tree/)
---
# My Solution
## Solution 1
### The Key Idea for Solving This Coding Question
Because root has no parent, it is the only node has 0 indegree in the n-ary tree.
### C++ Code

class Solution {
public:
    Node *findRoot(vector<Node *> &tree) {
        unordered_map<Node *, int> indegree;
        for (Node *node : tree) {
            auto iter = indegree.find(node);
            if (iter == indegree.end()) {
                indegree[node] = 0;
            }

            for (Node *child : node->children) {
                ++indegree[child];
            }
        }

        for (auto &x : indegree) {
            if (x.second == 0) {
                return x.first;
            }
        }

        return nullptr;
    }

};

### Time Complexity
$O(n)$
$n$ is the number of nodes in the n-ary tree.
### Space Complexity
$O(n)$
$n$ is the number of nodes in the n-ary tree.
## Solution 2
### The Key Idea for Solving This Coding Question
Find the node that appears only once.
Because during the traversal, except the root, all the node will be visited twice. The first time is the parent visiting all its children. The second time will be the child become parent and visit its children.
### C++ Code

class Solution {
public:
    Node *findRoot(vector<Node *> tree) {
        int rootVal = 0;
        for (Node *node : tree) {
            rootVal ^= node->val;

            for (Node *child : node->children) {
                rootVal ^= child->val;
            }
        }

        Node *root = nullptr;
        for (Node *node : tree) {
            if (node != nullptr && node->val == rootVal) {
                root = node;
                break;
            }
        }

        return root;
    }
};

### Time Complexity
$O(n)$
$n$ is the number of nodes in the n-ary tree.
### Space Complexity
$O(1)$
# Miscellane
<!--
# Test Cases

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

[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]

-->