How to Find Root of N-Ary Tree using the Hash Set?

Given all the nodes of an N-ary tree as an array Node[] tree where each node has a unique value. Find and return the root of the N-ary tree. Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Follow up: Can you find the root of the tree with O(1) additional memory space?

Notes:
The following input is only given to testing purposes.
You will receive as input a list of all nodes of the n-ary tree in any order.

n-ary-tree

Example 1:
Input: [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]

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

Hints:
Node with indegree 0 is the root

Using Hash Set to Find the Root of N-ary tree

We can add all the nodes into a hash set. Then we can remove children nodes from the set. The last (and only) node left in the set will be the root.

/*
// 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) {
        unordered_set<Node*> nodes;
        for (const auto &n: tree) {
            nodes.insert(n);
        }
        for (const auto &n: tree) {
            for (const auto &c: n->children) {
                nodes.erase(c);
            }
        }
        return *begin(nodes);
    }
};

O(N) running time (two passes), and O(N) space. We can slightly improve (early exit) by swapping the two loops: first add all the children nodes into the set, then we can go through the tree nodes to see which one does not appear in the set – that must be a root node.

/*
// 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) {
        unordered_set<Node*> nodes;
        for (const auto &n: tree) {
            for (const auto &c: n->children) {
                nodes.insert(c);
            }
        }
        for (const auto &n: tree) {
            if (!nodes.count(n)) {
                return n;
            }
        }
        return nullptr;
    }
};

Using Math to Find the Root of the N-ary Tree with O(1) constant space

Given each node has a unique value/number, we can compute the sum of all nodes and sum of all children nodes. Thus the root must have a value which equals to the difference.

/*
// 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 sum = 0;
        int allChildren = 0;
        for (const auto &n: tree) {
            sum += n->val;
            for (const auto &c: n->children) {
                allChildren += c->val;
            }
        }
        for (const auto &n: tree) {
            if (n->val == sum - allChildren) {
                return n;
            }
        }
        return nullptr;
    }
};

O(1) constant space, and O(N) time. However this approach can not be generalized.

See also Python code for finding the root of the N-ary tree: Teaching Kids Programming – Find Root of N-Ary Tree using Hash Set

–EOF (The Ultimate Computing & Technology Blog) —