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).

Examples

Example 1:

graph TD
  1 --- A[3] & B[2] & C[4]
  A --- 5 & 6

(have to use A, B, C in mermaid to make the ordering of nodes better)

1
2

Input: root = [1,null,3,2,4,null,5,6]
Output: [[1],[3,2,4],[5,6]]

Example 2:

graph TD
  1 --- 2 & 3 & 4 & 5
  3 --- 6 & 7
  7 --- 11
  11 --- 14
  4 --- 8
  8 --- 12
  5 --- 9 & 10
  9 --- 13
  
1
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]]

Solution

Method 1 - BFS

The goal is to perform a level-order traversal on an n-ary tree, which is essentially visiting the nodes level by level. The challenge arises because the tree is n-ary, meaning each node can have multiple children, unlike a binary tree with only two children.

The breadth-first search (BFS) approach is ideal for this problem as it inherently processes nodes level by level. Here’s the step-by-step approach:

  • Use a queue to traverse nodes level by level.
  • Start with the root node in the queue.
  • For each level, process all nodes in the queue, collect their values, and enqueue their children.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public List<List<Integer>> levelOrder(Node root) {

	List<List<Integer>> ans = new ArrayList<>();
	if (root == null) {
		return ans;
	}

	Queue<Node> queue = new ArrayDeque<>();
	queue.add(root);

	while (!queue.isEmpty()) {
		int size = queue.size();
		List<Integer> currLevel = new ArrayList<>();
		while (size > 0) {
			Node node = queue.poll();
			currLevel.add(node.val);
			if (node.children != null) {
				queue.addAll(node.children);
			}
			size--;
		}
		ans.add(currLevel);
	}
	return ans;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def levelOrder(self, root: Optional[Node]) -> List[List[int]]:
        ans: List[List[int]] = []
        if not root:
            return ans
        
        q = deque([root])  # Queue to hold nodes to be processed
        
        while q:
            lvl_vals: List[int] = []
            size: int = len(q)
            for _ in range(size):
                curr = q.popleft()
                curr_level.append(curr.val)
                q.extend(curr.children)  # Add all children of current node to the queue
            ans.append(curr_level)
        
        return ans

Complexity

  • ⏰ Time complexity: O(n), where n is the total number of nodes. Each node is visited once during traversal.
  • 🧺 Space complexity: O(n), for storing nodes in the queue.