N-ary Tree Level Order Traversal
The key idea
Process the tree one level at a time. Before expanding, record how many nodes are currently in the queue — that count is exactly the size of the current level. Dequeue that many nodes into one group and enqueue all their children for the next round.
Problem
Given an n-ary tree, return the level order traversal of its nodes' values.
In an n-ary tree each node may have any number of children, given left-to-right. Level order means you visit the nodes level by level, top to bottom, and within a level you read them left to right. The result is a list of lists: one inner list per level.
The input root is serialized in level order, with each group of children separated by a null value. An empty tree returns an empty list [].
Constraints
- The height of the n-ary tree is less than or equal to
1000 - The total number of nodes is between
[0, 10^4]
Examples
Input: root = [1,null,3,2,4,null,5,6]
Output: [[1],[3,2,4],[5,6]]
Input: root = [1,null,2,3,4]
Output: [[1],[2,3,4]]
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More BFS / DFS problems
- 01 MatrixMEDIUM
- Average of Levels in Binary TreeEASY
- Binary Tree Level Order TraversalMEDIUM
- Binary Tree Level Order Traversal IIMEDIUM
- Binary Tree Right Side ViewMEDIUM
- Binary Tree Zigzag Level Order TraversalMEDIUM
- Find Bottom Left Tree ValueMEDIUM
- Find Largest Value in Each Tree RowMEDIUM
- Flood FillEASY
- Keys and RoomsMEDIUM
- Max Area of IslandMEDIUM
- Maximum Level Sum of a Binary TreeMEDIUM