Skip to main content

429 - N-ary Tree Level Order Traversal

Difficulty: Medium | Pattern: Tree BFS | Company tags: Amazon, Google, Facebook

Problem Statement​

Given an n-ary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level).

Nary-Tree input serialization is represented in their level order, with each group of children separated by null.

Example:

Input: root = [1,null,3,2,4,null,5,6]
Output: [[1],[3,2,4],[5,6]]

Algorithm Flow​

Solution: BFS — O(n), O(w)​

from collections import deque

def levelOrder(root) -> list[list[int]]:
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            for child in node.children:
                queue.append(child)
        result.append(level)
    
    return result

Dry Run​

Tree: 1 → children [3,2,4]; 3 → children [5,6]

LevelQueue startLevel valuesQueue end
0[1][1][3,2,4]
1[3,2,4][3,2,4][5,6]
2[5,6][5,6][]

Result: [[1],[3,2,4],[5,6]] ✓

ProblemKey difference
LC 102 Binary Tree Level OrderBinary tree (2 children max)
LC 429 N-ary Level OrderN children per node
LC 637 Average of LevelsAverage instead of collect

Edge Cases​

  • Empty tree → []
  • Single root with no children → [[root.val]]

Complexity​

  • Time: O(n) — visit all nodes
  • Space: O(w) where w is max width

Key Terms​

TermDefinition
BFS (Breadth-First Search)Traversal that visits nodes level by level using a FIFO queue.
Level size snapshotCapturing len(queue) before the inner loop so only the current level's nodes are processed, not children added during the loop.
N-ary treeA tree where each node can have any number of children, stored as a list (node.children) rather than fixed left/right pointers.
Queue (deque)FIFO structure enabling O(1) append/popleft, essential for efficient BFS.

FAQ​

Q: Can this be solved with DFS instead of BFS? A: Yes — track depth as a parameter and append node.val into result[depth], creating the list if it doesn't exist yet; it produces the same grouping but via recursion instead of a queue.

Q: What if the tree is empty (root is None)? A: The function returns [] immediately via the guard clause, no queue operations needed.

Q: How does this differ from binary tree level order traversal (LC 102)? A: Instead of checking two fixed children (left, right), you iterate over node.children, a list of arbitrary length — the queue/loop logic is otherwise identical.

Q: Why snapshot len(queue) before the inner for-loop? A: Without it, children pushed during the loop would be counted as part of the same level, mixing levels together.

Q: What's the space complexity in the worst case? A: O(w) for the queue where w is the maximum width of any level, but O(n) is used for the output since every node value is stored in result.

Quick Revision​

  • Goal: group node values by depth level, left to right.
  • Use BFS with a queue seeded with the root.
  • Before processing a level, snapshot len(queue) — that's how many nodes belong to the current level.
  • Pop that many nodes, record their values, and enqueue their children (node.children, not left/right).
  • Append the collected level list to the result after each full level.
  • Time O(n) — every node visited once; space O(w) for the queue at the widest level.
  • Empty tree → return [] immediately.
  • Same skeleton as binary tree level order traversal, generalized to arbitrary child counts.