# LeetCode 429: N-ary Tree Level Order Traversal

## Problem Restatement

We are given the root of an N-ary tree.

We need to return the level order traversal of its node values.

Level order traversal means:

1. Visit all nodes on level `0`
2. Then all nodes on level `1`
3. Then all nodes on level `2`
4. Continue until the tree is finished

For each level, we store the node values in a separate list.

The final answer is therefore a list of lists.

For example:

```text
        1
      / | \
     3  2  4
    / \
   5   6
```

The traversal becomes:

```python
[
    [1],
    [3, 2, 4],
    [5, 6],
]
```

The official problem asks for level order traversal of an N-ary tree and expects the result grouped by depth level. ([leetcode.com](https://leetcode.com/problems/n-ary-tree-level-order-traversal/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Root node of an N-ary tree |
| Output | List of levels |
| Each level | List of node values at the same depth |
| Empty tree | Return `[]` |

The node structure is usually:

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

## Examples

Consider this tree:

```text
        1
      / | \
     3  2  4
    / \
   5   6
```

Level `0` contains:

```text
1
```

Level `1` contains:

```text
3, 2, 4
```

Level `2` contains:

```text
5, 6
```

So the answer is:

```python
[
    [1],
    [3, 2, 4],
    [5, 6],
]
```

For a single-node tree:

```text
1
```

the result is:

```python
[[1]]
```

For an empty tree:

```python
root = None
```

the result is:

```python
[]
```

## First Thought: DFS by Depth

One possible approach is DFS.

During recursion, we track the current depth:

```python
dfs(node, depth)
```

When we visit a node, we append its value into:

```python
result[depth]
```

This works.

However, level order traversal is naturally a breadth-first traversal problem, so BFS is simpler and more direct.

## Key Insight

Breadth-first search visits nodes level by level.

A queue naturally maintains this order.

The process is:

1. Put the root into the queue.
2. Process all nodes currently inside the queue.
3. Those nodes form one level.
4. Push all their children into the queue.
5. Repeat.

The important trick is:

```python
level_size = len(queue)
```

At the beginning of each iteration, the queue contains exactly the nodes for the current level.

So we process exactly `level_size` nodes before moving to the next level.

## Algorithm

Handle the empty tree first:

```python
if not root:
    return []
```

Create:

```python
queue = deque([root])
result = []
```

While the queue is not empty:

1. Compute the current level size.
2. Create an empty list for the current level.
3. Remove exactly `level_size` nodes.
4. Append their values to the current level list.
5. Push all children into the queue.
6. Append the completed level list into the answer.

Finally return the result.

## Correctness

At the start of each loop iteration, the queue contains exactly the nodes from one tree level.

This is true initially because the queue contains only the root node, which is level `0`.

Suppose the queue currently contains exactly all nodes at depth `d`.

We compute:

```python
level_size = len(queue)
```

and process exactly those `level_size` nodes.

While processing them, we append all their children into the queue. Every child of a depth `d` node has depth `d + 1`.

Therefore, after processing the current level, the queue contains exactly all nodes at depth `d + 1`.

By induction, every iteration processes exactly one level in left-to-right order.

Each node value is appended into the list corresponding to its depth, so the returned structure is the correct level order traversal.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Every node is visited once |
| Space | `O(n)` | The queue may contain many nodes at one level |

Here, `n` is the number of nodes in the tree.

## Implementation

```python
from collections import deque

class Solution:
    def levelOrder(self, root: 'Node') -> list[list[int]]:
        if not root:
            return []

        result = []
        queue = deque([root])

        while queue:
            level_size = len(queue)
            level = []

            for _ in range(level_size):
                node = queue.popleft()

                level.append(node.val)

                for child in node.children:
                    queue.append(child)

            result.append(level)

        return result
```

## Code Explanation

We first handle the empty tree:

```python
if not root:
    return []
```

Then we initialize the BFS queue:

```python
queue = deque([root])
```

The queue stores nodes waiting to be processed.

The main BFS loop continues while nodes still exist:

```python
while queue:
```

At the start of each iteration:

```python
level_size = len(queue)
```

This tells us how many nodes belong to the current level.

We create a list for this level:

```python
level = []
```

Then we process exactly `level_size` nodes:

```python
for _ in range(level_size):
```

Each node is removed from the front:

```python
node = queue.popleft()
```

We store its value:

```python
level.append(node.val)
```

Then we push all children into the queue:

```python
for child in node.children:
    queue.append(child)
```

After the loop finishes, `level` contains all node values from one depth level.

We append it into the final answer:

```python
result.append(level)
```

Finally, we return all levels.

## Testing

We can build several trees and verify the traversal output.

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

def run_tests():
    s = Solution()

    root = Node(1, [
        Node(3, [
            Node(5),
            Node(6),
        ]),
        Node(2),
        Node(4),
    ])

    assert s.levelOrder(root) == [
        [1],
        [3, 2, 4],
        [5, 6],
    ]

    single = Node(10)
    assert s.levelOrder(single) == [[10]]

    assert s.levelOrder(None) == []

    chain = Node(1, [
        Node(2, [
            Node(3, [
                Node(4),
            ]),
        ]),
    ])

    assert s.levelOrder(chain) == [
        [1],
        [2],
        [3],
        [4],
    ]

    wide = Node(1, [
        Node(2),
        Node(3),
        Node(4),
        Node(5),
    ])

    assert s.levelOrder(wide) == [
        [1],
        [2, 3, 4, 5],
    ]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Checks normal BFS traversal |
| Single node | Checks smallest non-empty tree |
| Empty tree | Checks `None` handling |
| Deep chain | Checks many levels |
| Wide level | Checks multiple siblings on the same level |