LeetCode Solutions Blog

N-ary Tree Level Order Traversal

Number: 764

Difficulty: Medium

Paid? No

Problem Description

Given an n-ary tree, return the level order traversal of its nodes' values. The tree is represented in level order where each group of children is separated by a null value.

Key Insights

Use Breadth-First Search (BFS) to traverse the tree level by level.
A queue data structure is ideal for maintaining the order of nodes to be processed.
Process all nodes at the current level before moving to the next, collecting their values.
Enqueue the children of each node so that they are processed in subsequent levels.

Space and Time Complexity

Time Complexity: O(N), since every node is processed exactly once. Space Complexity: O(N), due to the queue holding up to all nodes at the last level in the worst-case scenario.

Solution

We use a BFS approach starting with the root node. At each level, record the number of nodes (the current size of the queue), process them, and enqueue their children. This results in a list of lists where each inner list contains the values of nodes at that level.

Code Solutions

# Node class definition for the n-ary tree.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

# Function to perform level order traversal of an n-ary tree.
def levelOrder(root):
    if not root:
        return []
    
    result = []       # This will store the final list of levels.
    queue = [root]    # Initialize the queue with the root node.
    
    # Process nodes level by level.
    while queue:
        level_size = len(queue)  # Number of nodes at the current level.
        current_level = []
        
        # Process each node in the current level.
        for _ in range(level_size):
            node = queue.pop(0)  # Dequeue the first node.
            current_level.append(node.val)  # Record the value of the node.
            
            # Enqueue all children of the current node.
            for child in node.children:
                queue.append(child)
        
        # Append the current level to the result.
        result.append(current_level)
    
    return result

# Example Usage:
# root = Node(1, [Node(3, [Node(5), Node(6)]), Node(2), Node(4)])
# print(levelOrder(root))  # Expected output: [[1], [3, 2, 4], [5, 6]]