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:

        1
      / | \
     3  2  4
    / \
   5   6

The traversal becomes:

[
    [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)

Input and Output

The node structure is usually:

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:

        1
      / | \
     3  2  4
    / \
   5   6

Level 0 contains:

1

Level 1 contains:

3, 2, 4

Level 2 contains:

5, 6

So the answer is:

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

For a single-node tree:

1

the result is:

[[1]]

For an empty tree:

root = None

the result is:

[]

First Thought: DFS by Depth

One possible approach is DFS.

During recursion, we track the current depth:

dfs(node, depth)

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

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:

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:

if not root:
    return []

Create:

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:

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

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

Implementation

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:

if not root:
    return []

Then we initialize the BFS queue:

queue = deque([root])

The queue stores nodes waiting to be processed.

The main BFS loop continues while nodes still exist:

while queue:

At the start of each iteration:

level_size = len(queue)

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

We create a list for this level:

level = []

Then we process exactly level_size nodes:

for _ in range(level_size):

Each node is removed from the front:

node = queue.popleft()

We store its value:

level.append(node.val)

Then we push all children into the queue:

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:

result.append(level)

Finally, we return all levels.

Testing

We can build several trees and verify the traversal output.

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: