LeetCode 429 - N-ary Tree Level Order Traversal

The problem asks us to perform a level order traversal of an n-ary tree. In other words, we need to return the values of the tree nodes grouped by their depth. The root node represents level 0, its immediate children are level 1, their children are level 2, and so on.

leetcodemediumtreebreadth-first-search

LeetCode Problem 429

Difficulty: 🟡 Medium
Topics: Tree, Breadth-First Search

Solution

Problem Understanding

The problem asks us to perform a level order traversal of an n-ary tree. In other words, we need to return the values of the tree nodes grouped by their depth. The root node represents level 0, its immediate children are level 1, their children are level 2, and so on.

The input is an n-ary tree represented by nodes where each node can have zero or more children. The tree is serialized using a level order format where null separates groups of children. The output is a list of lists, where each inner list contains the values of nodes at a particular depth.

Constraints provide useful information: the height of the tree is at most 1000, and there can be up to 10,000 nodes. This means the algorithm needs to handle relatively deep trees but does not require handling extremely wide trees beyond 10,000 nodes.

Important edge cases include an empty tree (root is None), a tree where some nodes have no children, or a tree that is heavily skewed (all nodes on one branch). The problem guarantees a valid n-ary tree input, so we do not need to handle invalid structures.

Approaches

A brute-force approach would attempt a recursive traversal without separating levels. One might perform a pre-order or post-order traversal and then group values afterward by tracking depths with an auxiliary list. While this works in theory, it requires traversing the tree and then performing extra operations to group by depth, which is less efficient in both time and space.

The optimal approach is to use Breadth-First Search (BFS). BFS naturally traverses the tree level by level. By using a queue, we can dequeue nodes of a given level, record their values, and enqueue their children for the next level. This ensures that each level is handled separately and efficiently, avoiding the need for additional grouping steps.

Approach Time Complexity Space Complexity Notes
Brute Force O(N) O(N) Traverse all nodes, then group by depth using extra memory.
Optimal O(N) O(N) BFS directly processes nodes level by level using a queue.

Algorithm Walkthrough

  1. Initialize an empty list result to store the final output. This will hold sublists for each level of the tree.

  2. If the root is None, return the empty result immediately as the tree is empty.

  3. Initialize a queue and enqueue the root node. This queue will help us process nodes level by level.

  4. While the queue is not empty, repeat the following steps:

  5. Determine the number of nodes at the current level by measuring the queue size.

  6. Initialize an empty list current_level to store values of nodes at this level.

  7. Dequeue nodes one by one according to the level size. For each node, append its value to current_level.

  8. Enqueue all children of the current node into the queue to process them in the next iteration.

  9. After processing all nodes of the current level, append current_level to result.

  10. After the queue is empty, return result.

Why it works: BFS guarantees that nodes are visited level by level. By keeping track of the current queue size, we isolate nodes at each depth. The invariant is that the queue always contains all nodes for the next level before we start processing them, ensuring the output list correctly represents the tree level order traversal.

Python Solution

from typing import List, Optional

"""
# Definition for a Node.
class Node:
    def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
        self.val = val
        self.children = children
"""

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        result: List[List[int]] = []
        if not root:
            return result
        
        from collections import deque
        queue = deque([root])
        
        while queue:
            level_size = len(queue)
            current_level: List[int] = []
            
            for _ in range(level_size):
                node = queue.popleft()
                current_level.append(node.val)
                if node.children:
                    queue.extend(node.children)
            
            result.append(current_level)
        
        return result

Explanation: We initialize the result list and a queue containing the root. For each level, we measure the number of nodes to process. We iterate through the nodes at that level, record their values, and enqueue their children for the next level. The BFS ensures we process each level sequentially and capture all node values correctly.

Go Solution

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func levelOrder(root *Node) [][]int {
    var result [][]int
    if root == nil {
        return result
    }
    
    queue := []*Node{root}
    
    for len(queue) > 0 {
        levelSize := len(queue)
        var currentLevel []int
        
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            currentLevel = append(currentLevel, node.Val)
            if node.Children != nil {
                queue = append(queue, node.Children...)
            }
        }
        
        result = append(result, currentLevel)
    }
    
    return result
}

Explanation: Go requires careful handling of slices. We initialize a queue with the root. For each level, we track its size, remove nodes from the front of the slice, append their values, and enqueue children using append. Nil checks prevent panics when a node has no children.

Worked Examples

Example 1: Input [1,null,3,2,4,null,5,6]

Step Queue State Current Level Result
Initial [1] [] []
Level 0 [] [1] [[1]]
Level 1 [3,2,4] [3,2,4] [[1],[3,2,4]]
Level 2 [5,6] [5,6] [[1],[3,2,4],[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]

Step Queue State Current Level Result
Level 0 [1] [1] [[1]]
Level 1 [2,3,4,5] [2,3,4,5] [[1],[2,3,4,5]]
Level 2 [6,7,8,9,10] [6,7,8,9,10] [[1],[2,3,4,5],[6,7,8,9,10]]
Level 3 [11,12,13] [11,12,13] [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13]]
Level 4 [14] [14] [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

Complexity Analysis

Measure Complexity Explanation
Time O(N) Each node is visited exactly once.
Space O(N) Queue can hold at most all nodes at one level in the worst case.

The complexity is linear in the number of nodes because BFS touches each node once, and the queue grows proportional to the maximum width of the tree, which can be up to N in the worst case.

Test Cases

# Provided examples
assert Solution().levelOrder(None) == []  # Empty tree
assert Solution().levelOrder(Node(1, [Node(3, [Node(5), Node(6)]), Node(2), Node(4)])) == [[1],[3,2,4],[5,6]]
assert Solution().levelOrder(Node(1, [Node(2), Node(3), Node(4), Node(5, [Node(6), Node(7), Node(8, [Node(9), Node(10, [Node(11), Node(12), Node(13, [Node(14)])])])])])) == [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

# Single node tree
assert Solution().levelOrder(Node(42)) == [[42]]

# Skewed tree
assert Solution().levelOrder(Node(1, [Node(2, [Node(3, [Node(4)])])])) == [[1],[2],[3],[4]]

# Nodes with empty children lists
assert Solution().levelOrder(Node(1, [Node(2, []), Node(3, []), Node(4, [])])) == [[1],[2,3,4]]
Test Why
Empty tree Validates handling of None input
Example 1 Standard multi-level tree
Example 2 Complex tree with multiple levels
Single node Checks minimal tree case
Skewed tree Ens