N Ary Tree Level Order Traversal - Leetcode Solution

Problem Statement

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

Solution

The problem can be solved using BFS algorithm. We can create a queue and push the root node to the queue. Then, we can remove the nodes from the queue one by one and add its children to the queue. Each time we remove a node from the queue, we can add its value to a list. We can continue this until the queue is empty.

We can use a variable count to keep track of the number of nodes in the current level. Initially, count will equal to 1, as we have only the root node at the first level. We can add null to the queue to separate the levels. Each time we remove a node from the queue, we can decrement the count. When count becomes 0, we know that we have processed all the nodes in the current level and we can add the list of values to the result list.

Python Code

Here is the Python code to solve this problem:

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root:
            return []
        
        queue = collections.deque()
        queue.append(root)
        queue.append(None)
        
        result = []
        current_level = []
        count = 1
        
        while queue:
            node = queue.popleft()
            count -= 1
            
            if node:
                current_level.append(node.val)
            
                for child in node.children:
                    queue.append(child)

            if count == 0:
                result.append(current_level)
                current_level = []
                count = len(queue)
                
                if queue:
                    queue.append(None)
        
        return result

Time Complexity

The time complexity of this solution is O(n), where n is the total number of nodes in the n-ary tree. We visit each node exactly once using BFS algorithm. The time complexity of appending and popping elements from a deque is O(1).

Space Complexity

The space complexity of this solution is O(n), where n is the total number of nodes in the n-ary tree. We are using a deque to store the nodes in the queue. The maximum number of nodes that can be in the queue at any point is the number of nodes at the last level of the tree, which is at most n/2 for a balanced n-ary tree. In addition to that, we are also using a list to store the result, which can have n elements, and a list to store the values of nodes in the current level, which can also have n elements. Therefore, the total space complexity is O(n).

1