Skip to main content
Talentd

N-ary Tree Level Order Traversal - Solution & Explanation

MediumTreeBreadth-First Search19 min readAsked at: Amazon, Microsoft, Google
Practice this problem

Problem Statement

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.

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.

Code

PythonJavaC++C

Python

Java

C++

C

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

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:

  1. Create an empty list t to store the values of the current level nodes.
  2. For each node in the queue, add its value to t and add its child nodes to the queue.
  3. Add 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n), as we store the entire tree in the queue and result list in the worst case.

Approach 2: Recursive Level Order Traversal

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.

BFS—
DFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Level Order Traversal using QueueO(n)O(w)Standard level order traversal. Best choice for interviews and large trees.
Recursive Level Order TraversalO(n)O(h)When you prefer DFS with depth tracking or want a concise recursive implementation.

Video Solution

N array Tree Level Order Traversal | Leetcode 429 | Live coding session 🌳🌳🌳 • Coding Decoded • 3,021 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice N-ary Tree Level Order Traversal with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Level Order Traversal

Next

N-ary Tree Postorder Traversal