N-ary Tree Level Order Traversal solution and explanation
Google
9 more videos on this problem
N array Tree Level Order Traversal | Leetcode 429 | Live coding session 🌳🌳🌳Coding Decoded · 6:15 · 3K views
Leetcode - N-ary Tree Level Order Traversal (Python)Timothy H Chang · 2:58 · 2K views
LEETCODE 429 (JAVASCRIPT) | N-ARY TREE LEVEL ORDER TRAVERSALAndy Gala · 8:35 · 2K views
Leetcode 429 N-Ary Tree Level Order Traversal (Java)TheAnalyticGuy · 2:42 · 750 views
429. N-ary Tree Level Order Traversal | Leetcode MediumJOY of LIFE · 16:20 · 695 views
N-ary Tree Level Order Traversal | Python3 BFS Solution, ExplainedTanishq Chaudhary · 6:46 · 502 views
N-ary Tree Level Order Traversal | C++ | Leetcode Solution 429Gantavya Malviya · 11:10 · 307 views
N Array Tree Level Order Traversal - LeetCode 429 - JavaScriptAlgoJS · 4:45 · 303 views
Daily Leetcode #888: Sep 05, 2022 - 429. N-ary Tree Level Order TraversalProgramming Live with Larry · 5:52 · 248 views
Leetcode429: N-ary Tree Level Order TraversalOnline School Of Math · 11:16 · 192 views
The problem
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:
- The height of the n-ary tree is less than or equal to
1000 - The total number of nodes is between
[0, 104]
Approach overview
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.
Approach 1: Approach 1: Iterative Level Order Traversal using Queue
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.
from collections import deque
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children if children is not None else []
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level_nodes = []
for _ in range(level_size):
current = queue.popleft()
level_nodes.append(current.val)
for child in current.children:
queue.append(child)
result.append(level_nodes)
return resultimport java.util.*;
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
}
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> levelNodes = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
Node current = queue.poll();
levelNodes.add(current.val);
if (current.children != null) {
queue.addAll(current.children);
}
}
result.add(levelNodes);
}
return result;
}
}#include <vector>
#include <queue>
using namespace std;
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> result;
if (!root) return result;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
vector<int> levelNodes;
for (int i = 0; i < levelSize; ++i) {
Node* node = q.front();
q.pop();
levelNodes.push_back(node->val);
for (Node* child : node->children) {
q.push(child);
}
}
result.push_back(levelNodes);
}
return result;
}
};#include <stdio.h>
#include <stdlib.h>
// Definition for a Node.
struct Node {
int val;
int numChildren;
struct Node** children;
};
struct Node** queue;
int head = 0, tail = 0;
void enqueue(struct Node* node) {
queue[tail++] = node;
}
struct Node* dequeue() {
return queue[head++];
}
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int** levelOrder(struct Node* root, int** columnSizes, int* returnSize) {
if (!root) {
*returnSize = 0;
return NULL;
}
queue = (struct Node**)malloc(10000 * sizeof(struct Node*));
int** result = (int**)malloc(1000 * sizeof(int*));
*columnSizes = (int*)malloc(1000 * sizeof(int));
*returnSize = 0;
enqueue(root);
while (head < tail) {
int levelSize = tail - head;
result[*returnSize] = (int*)malloc(levelSize * sizeof(int));
for (int i = 0; i < levelSize; ++i) {
struct Node* node = dequeue();
result[*returnSize][i] = node->val;
for (int j = 0; j < node->numChildren; ++j) {
enqueue(node->children[j]);
}
}
(*columnSizes)[*returnSize] = levelSize;
(*returnSize)++;
}
free(queue);
return result;
}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.
Approach 2: Approach 2: Recursive Level Order Traversal
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.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children if children is not None else []
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
def traverse(node, level):
if not node:
return
if len(result) == level:
result.append([])
result[level].append(node.val)
for child in node.children:
traverse(child, level + 1)
result = []
traverse(root, 0)
return resultimport java.util.*;
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
}
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> result = new ArrayList<>();
traverse(root, 0, result);
return result;
}
private void traverse(Node node, int level, List<List<Integer>> result) {
if (node == null) return;
if (result.size() <= level) {
result.add(new ArrayList<>());
}
result.get(level).add(node.val);
for (Node child : node.children) {
traverse(child, level + 1, result);
}
}
}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.
Approach 3: BFS
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:
- Create an empty list
tto store the values of the current level nodes. - For each node in the queue, add its value to
tand add its child nodes to the queue. - Add
tto the result listans.
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.
/**
* Definition for node.
* class Node {
* val: number
* children: Node[]
* constructor(val?: number) {
* this.val = (val===undefined ? 0 : val)
* this.children = []
* }
* }
*/
function levelOrder(root: Node | null): number[][] {
const ans: number[][] = [];
if (!root) {
return ans;
}
const q: Node[] = [root];
while (q.length) {
const qq: Node[] = [];
const t: number[] = [];
for (const { val, children } of q) {
qq.push(...children);
t.push(val);
}
ans.push(t);
q.splice(0, q.length, ...qq);
}
return ans;
}/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func levelOrder(root *Node) (ans [][]int) {
if root == nil {
return
}
q := []*Node{root}
for len(q) > 0 {
var t []int
for n := len(q); n > 0; n-- {
root = q[0]
q = q[1:]
t = append(t, root.Val)
for _, child := range root.Children {
q = append(q, child)
}
}
ans = append(ans, t)
}
return
}Approach 4: DFS
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.
/**
* Definition for node.
* class Node {
* val: number
* children: Node[]
* constructor(val?: number) {
* this.val = (val===undefined ? 0 : val)
* this.children = []
* }
* }
*/
function levelOrder(root: Node | null): number[][] {
const ans: number[][] = [];
const dfs = (root: Node | null, i: number) => {
if (root === null) {
return;
}
if (ans.length <= i) {
ans.push([]);
}
const { val, children } = root;
ans[i++].push(val);
children.forEach(node => dfs(node, i));
};
dfs(root, 0);
return ans;
}/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func levelOrder(root *Node) (ans [][]int) {
var dfs func(root *Node, i int)
dfs = func(root *Node, i int) {
if root == nil {
return
}
if len(ans) <= i {
ans = append(ans, []int{})
}
ans[i] = append(ans[i], root.Val)
for _, child := range root.Children {
dfs(child, i+1)
}
}
dfs(root, 0)
return
}Complexity comparison
| 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 | – |
Complexity analysis
| 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. |
Frequently asked questions
Is N-ary Tree Level Order Traversal easy or hard?
This problem is usually rated Medium because the core BFS idea is simple but requires handling a variable number of children for each node. Candidates comfortable with binary tree level order traversal can adapt the same pattern to N-ary trees quickly.
N-ary Tree Level Order Traversal Python/Java solution
Python and Java solutions typically implement BFS with a queue (collections.deque in Python or LinkedList/ArrayDeque in Java). The algorithm processes nodes level by level and collects values into nested lists representing each depth. Both implementations run in O(n) time and O(w) space.
How to solve N-ary Tree Level Order Traversal in O(n)?
Use Breadth-First Search with a queue. Start by pushing the root node into the queue, then repeatedly process nodes level by level using the queue size to separate levels. For each node, append its value to the current level list and enqueue all its children. Since each node is processed once, the total runtime remains O(n).
What is the best approach for N-ary Tree Level Order Traversal?
The best approach is Breadth-First Search (BFS) using a queue. BFS naturally processes nodes level by level, which matches the requirement of level order traversal. Each level is processed by iterating the current queue size and pushing all children of those nodes. This approach runs in O(n) time and uses O(w) space where w is the maximum width of the tree.
Is N-ary Tree Level Order Traversal asked at Google/Amazon/Meta?
Level order traversal problems are common in interviews at companies like Amazon, Google, and Meta because they test tree traversal fundamentals and BFS understanding. Variants appear in many interview question banks, especially when working with N-ary trees or graph-like structures.
What data structure is used in N-ary Tree Level Order Traversal?
A queue is the primary data structure used for the iterative solution. The queue stores nodes of the current level while their children are added for the next level. This structure enables first-in-first-out processing required for breadth-first traversal.
What is the time complexity of N-ary Tree Level Order Traversal?
The time complexity is O(n) because every node in the N-ary tree is visited exactly once. Each node is dequeued once and its children are added to the queue once. The total operations scale linearly with the number of nodes.