We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

N-ary Tree Level Order Traversal

Difficulty: Medium

Problem Description

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

Key Insights

  • The problem requires traversing an n-ary tree level by level.
  • A breadth-first search (BFS) approach is suitable for level order traversal.
  • Each node can have multiple children, making it essential to handle child nodes dynamically.
  • The input serialization is represented in level order, with groups of children separated by null values.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, since we visit each node once. Space Complexity: O(W), where W is the maximum width of the tree, which can happen at any level during traversal.

Solution

To solve the problem, we will use a breadth-first search (BFS) algorithm. We will utilize a queue data structure to keep track of nodes as we process them level by level. For each node, we will add its children to the queue, and once we finish processing all nodes at the current level, we will store their values in a list. The process continues until there are no more nodes left to process.

Code Solutions

from collections import deque

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

def levelOrder(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            for child in node.children:
                queue.append(child)
        
        result.append(current_level)
    
    return result
← Back to All Questions