Given an n-ary tree, return the level order traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
Example 1:
Input: root = [1,null,3,2,4,null,5,6] Output: [[1],[3,2,4],[5,6]]
Example 2:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
Constraints:
1000[0, 104]Problem Overview: Given the root of an N-ary tree, return the level order traversal of its nodes' values. Nodes at the same depth should appear in the same list, processed from left to right.
Approach 1: Iterative Level Order Traversal using Queue (O(n) time, O(w) space)
This approach uses Breadth-First Search (BFS) with a queue to process the tree level by level. Start by pushing the root into the queue. For each level, record the current queue size, iterate that many nodes, and enqueue all children of each node. This guarantees that nodes are grouped by depth before moving to the next level. Time complexity is O(n) because every node is visited exactly once, and space complexity is O(w), where w is the maximum width of the tree due to the queue storing nodes of the current level.
This pattern appears frequently in Breadth-First Search problems and works naturally for level-based traversal. If you already think in BFS layers, this solution is straightforward and easy to implement.
Approach 2: Recursive Level Order Traversal (O(n) time, O(h) space)
The recursive approach uses Depth-First Search (DFS) while tracking the current depth. Maintain a result list where index i stores values for level i. During recursion, if the current depth does not yet exist in the result, create a new list. Append the node's value and recursively process each child with depth + 1. Each node is still visited once, giving O(n) time complexity. Space complexity becomes O(h) for the recursion stack, where h is the tree height.
This approach blends tree traversal with recursion. It avoids an explicit queue and keeps the implementation compact, though it may be less intuitive if you naturally think about levels iteratively.
Recommended for interviews: The queue-based BFS solution is the expected answer in most interviews because level order traversal directly maps to BFS mechanics. The recursive variant shows deeper understanding of traversal patterns, but interviewers typically prefer the iterative BFS since it clearly expresses level boundaries.
This approach uses a queue data structure to perform a breadth-first search (BFS) or level order traversal of an n-ary tree. The primary idea is to process each node starting from the root by visiting all children of the current node(s) before moving on to the next level. This is achieved by maintaining a queue that temporarily holds nodes to be processed at the current level while enqueueing their children for the next level.
This Python code defines a Node class to represent tree nodes and a Solution class with a levelOrder method for BFS traversal. A deque is used for the queue to facilitate O(1) pops from the front. The traversal iterates over each level, processes all nodes at the current level, and queues their children.
Time Complexity: O(n), where n is the number of nodes in the tree, since each node is visited once.
Space Complexity: O(n), as we store the entire tree in the queue and result list in the worst case.
A recursive approach uses a helper function to traverse the tree by maintaining a reference to the current level. The approach relies on depth-first search (DFS) to record nodes in their respective levels. The helper function is invoked for each node, and levels are tracked by an accumulated list of lists.
This recursive solution defines a helper function traverse that processes a node and records its value in the list associated with the current level. Recursion ensures that nodes are dealt with in a depth-first fashion, expanding each branch fully before moving to another sibling branch.
Time Complexity: O(n), with n being the total node count since we visit each node exactly once.
Space Complexity: O(n), accounting for the recursive call stack and the result storage.
First, we check if the root node is null. If it is, we return an empty list directly.
Otherwise, we create a queue q and initially add the root node to the queue.
When the queue is not empty, we loop through the following operations:
t to store the values of the current level nodes.t and add its child nodes to the queue.t to the result list ans.Finally, return the result list ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the N-ary tree.
Python
Java
C++
Go
TypeScript
We can use the Depth-First Search method to traverse the entire tree.
We define a helper function dfs(root, i), where root represents the current node, and i represents the current level.
In the dfs function, we first check if root is null. If it is, we return directly.
Otherwise, we check if the length of ans is less than or equal to i. If it is, it means that the current level has not been added to ans yet, so we need to add an empty list first. Then we add the value of root to ans[i].
Next, we traverse all child nodes of root. For each child node, we call dfs(child, i + 1).
In the main function, we call dfs(root, 0) and return ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the N-ary tree.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Level Order Traversal using Queue | Time Complexity: O(n), where n is the number of nodes in the tree, since each node is visited once. |
| Approach 2: Recursive Level Order Traversal | Time Complexity: O(n), with n being the total node count since we visit each node exactly once. |
| BFS | — |
| DFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Level Order Traversal using Queue | O(n) | O(w) | Standard level order traversal. Best choice for interviews and large trees. |
| Recursive Level Order Traversal | O(n) | O(h) | When you prefer DFS with depth tracking or want a concise recursive implementation. |
N array Tree Level Order Traversal | Leetcode 429 | Live coding session 🌳🌳🌳 • Coding Decoded • 2,949 views views
Watch 9 more video solutions →Practice N-ary Tree Level Order Traversal with our built-in code editor and test cases.
Practice on FleetCode