N-ary Tree Level Order Traversal
Medium · Trees · Tree · Breadth-First Search
Problem
An n-ary tree is a tree where each node has a value and a list of any number of children. Given its root, return the level order traversal of its values: a list of levels from top to bottom, each listed left to right.
The tree is written in level order, with each group of children followed by null as a separator. For example [1,null,3,2,4,null,5,6] is root 1 with children 3, 2, 4, and node 3 has children 5, 6. In Python, Node has val and children, and from_nary() builds the tree from such a list.
Examples
Input: root = [1,null,3,2,4,null,5,6] Output: [[1],[3,2,4],[5,6]]
Node 1 has children 3, 2, 4; node 3's children 5 and 6 form the third level.
Input: root = [1,null,2,3,4,null,5,null,6,null,7] Output: [[1],[2,3,4],[5,6,7]]
Nodes 2, 3 and 4 have one child each: 5, 6 and 7.
Input: root = [] Output: []
An empty tree has no levels.
Constraints
- The number of nodes is in the range [0, 10^4]
- The height of the tree is at most 1000
Approaches
- Depth-first, filed by depth — time O(n), space O(n)
Follow-up
The level-size trick is the same as for binary trees: only "add the children" changes, from two fixed slots to a list. The use cases read every other level backwards (zigzag) and keep only each level's largest value.
Related problems
Start free on Cariara · Coding problems · System design studio
