Coding Interview PatternsN-ary Tree Level Order Traversal
MediumTree Breadth-First Search

N-ary Tree Level Order Traversal

Explanation & Solution

Practice Problem

Description

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

Each node in the tree has a val (integer) and a children (array of child nodes).

The nary-tree input serialization is represented in level order traversal, where each group of children is separated by the null value.

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

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

Explanation:

  • Level 0: [1]
  • Level 1: [3, 2, 4]
  • Level 2: [5, 6]

Constraints

  • The height of the n-ary tree is less than or equal to 1000
  • The total number of nodes is in the range [0, 10⁴]
  • Each node's value is in the range [0, 10⁴]

Approach

Tree Breadth-First Search pattern

1. Handle Empty Tree

  • If root is null, return an empty array []

2. Initialize BFS

  • Create a result array to hold the final answer
  • Create a queue initialized with the root node
  • Use a head pointer for efficient dequeuing

3. Process Level by Level

  • While there are nodes in the queue:
  • Calculate levelSize — the number of nodes at the current level
  • Create a level array to collect values for this level
  • For each node in the current level:
  • Dequeue the node and push its val into level
  • Enqueue all of its children
  • Push the completed level array into result

4. Return Result

  • After BFS completes, result contains one sub-array per level
  • Return result

Key Insight

  • This is a standard BFS level-order traversal, adapted for n-ary trees
  • Instead of enqueueing left and right, we iterate over the children array
Time
O(n)every node is visited exactly once
Space
O(n)the queue may hold up to an entire level of nodes

Visualization

Input:
DFS Traversal[1, 3, 2, 4, 5, 6]
135
output0

Press play to start DFS traversal

CurrentIn stackComplete
7 steps

Solution Code

Previous
Cousins in Binary Tree
Next
Maximum Width of Binary Tree