Teaching Kids Programming – Find Root of N-Ary Tree using Hash Set

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Find Root of N-ary Tree using Hash Set

If we iterate all the nodes and add their children to a set, the root will be only node that isn’t in the hash set. The following Python code uses a Hash Set to remember all the children nodes, and a second pass finds the root which isn’t in the set.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

"""
# Definition for a Node.
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: List['Node']) -> 'Node':
        seen = set()
        for node in tree:
            for child in node.children:
                seen.add(child.val)
        
        for node in tree:
            if node.val not in seen:
                return node            

"""
# Definition for a Node.
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: List['Node']) -> 'Node':
        seen = set()
        for node in tree:
            for child in node.children:
                seen.add(child.val)
        
        for node in tree:
            if node.val not in seen:
                return node            

Time complexity O(N), space complexity is also O(N) since we are using a hash set – N is the number of the nodes in the N-nary tree.

We can also use the set difference (minus) and the list comprehension in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

"""
# Definition for a Node.
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: List['Node']) -> 'Node':
        seen = set()
        for node in tree:
            for child in node.children:
                seen.add(child)
        
        allNodes = set([x for x in tree])
        return list(allNodes-seen)[0]

"""
# Definition for a Node.
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: List['Node']) -> 'Node':
        seen = set()
        for node in tree:
            for child in node.children:
                seen.add(child)
        
        allNodes = set([x for x in tree])
        return list(allNodes-seen)[0]

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

–EOF (The Ultimate Computing & Technology Blog) —