Practice/Meta/Leetcode 429. N-ary Tree Level Order Traversal

Leetcode 429. N-ary Tree Level Order Traversal

CodingMust

Problem

Given the root of an n-ary tree (a tree where each node can have any number of children), return the values of its nodes organized by their depth level. The result should be a list of lists, where each inner list contains all node values at that particular level, ordered from left to right.

An n-ary tree is defined by a Node class with two properties:

• val: an integer representing the node's value
• children: a list of child nodes (which may be empty)

Traverse the tree level by level (also known as breadth-first traversal) and group all values at the same depth together.

Requirements

1. Return a list of lists where each inner list represents one level of the tree
2. Values within each level should be ordered from left to right as they appear in the tree
3. Handle empty trees (null/None root) by returning an empty list
4. Process all nodes exactly once

Constraints

• The number of nodes in the tree is in the range [0, 10000]
• Each node's value is between -100 and 100
• The tree height will not exceed 1000 levels
• Each node can have zero or more children (n-ary structure)

Examples

Example 1:

` Input: root = [1,null,3,2,4,null,5,6] Tree structure: 1 / |
3 2 4 /
5 6

Output: [[1], [3, 2, 4], [5, 6]] Explanation:

• Level 0: node with value 1
• Level 1: nodes with values 3, 2, 4 (left to right)
• Level 2: nodes with values 5, 6 (children of node 3) `

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] Tree structure: 1 / |
2 3 4 / \ | 6 7 8 / \ | | 11 12 13 14 / 9 / 10

Output: [[1], [2, 3, 4], [6, 7, 8], [11, 12, 13, 14], [9], [10]] `

Example 3:

Input: root = null Output: [] Explanation: Empty tree returns empty list