N-ary Tree Level Order Traversal — Medium

Medium

Given an n-ary tree, return the level order traversal of its nodes’ values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Example 1:

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

Example 2:

Input: root = [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],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

Constraints:

• The height of the n-ary tree is less than or equal to 1000
• The total number of nodes is between [0, 104]

Solution:

My solution makes use of hashmap which keeps track of the levels.

class Solution:

    def levelOrder(self, root: 'Node') -> List[List[int]]:
        hmap = {}
        level = 0
        queue = [(root, 1)]
        
        while queue:
            node, level = queue.pop()
            if node:
                queue.extend([(x, level+1) for x in node.children[::-1]]) 
            
                if level in hmap:
                    hmap[level] += [node.val]
                else:
                    hmap[level] = [node.val]
            
        return hmap.values()

O(n) time and O(n) space complexity.

Runtime: 56 ms, faster than 32.68% of Python3 online submissions for N-ary Tree Level Order Traversal.

Memory Usage: 16.2 MB, less than 12.63% of Python3 online submissions for N-ary Tree Level Order Traversal.

Solution

Recursive solution from Leetcode makes use of an array as a map. It uses the indexes of the array to represent the levels and adds the element to respective levels.

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        # using an array as a map, where the indices represent the levels
        # initialize result before calling traverse otherwise it will error on result not found.
        result = []
        
        def traverse(root, level):
            # make sure the length of the result is equal to the level
            # this is the ensure we have a new empty array for a new level
            if len(result) == level:
                result.append([])
            
            # append the value to the respective level
            result[level].append(root.val)
            
            # call recursively all the children with level + 1.
            for child in root.children:
                traverse(child, level+1)
        
        if root:
            traverse(root, 0)
        
        return result

• Time complexity : O(n)O(n), where nn is the number of nodes.
• Space complexity : O(log⁡n) average case and O(n) worst case. The space used is on the runtime stack.

Success

Runtime: 52 ms, faster than 64.93% of Python3 online submissions for N-ary Tree Level Order Traversal.

Memory Usage: 16.1 MB, less than 12.63% of Python3 online submissions for N-ary Tree Level Order Traversal.