1. Introduction

Given an n-ary tree, return the level order traversal of its nodes’ values (i.e., from left to right, level by level).

You can read about Binary Tree Traversals (DFS and BFS) here. https://justamonad.com/binary-tree-traversals/

2. Content

For level order traversal or Breadth first search traversal, we use an auxiliary data structure called Queue.

Example: Below is what an n-ary tree looks like.
Level Order Traversal is [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

3. Level Order Traversal

The idea behind BFS or level order traversal is that we explore all nodes at current depth and then move to the next depth level.Extra memory, i.e. Queue is used to keep track of nodes that are not yet explored.

1. Base condition. If input is null, then we return an empty list.

if(root == null) return Collections.emptyList();

2. As the result is a list of lists, we create a result as List<List<Integer>>.

List<List<Integer>> result = new ArrayList<>();

3. Initialize the Queue data structure to hold the nodes that need to be explored. Add a root node to it.

Deque<TreeNode> q = new ArrayDeque<>();
q.add(root);

4. While the Queue isn’t empty, traverse the nodes from the Queue. Once traversed, insert the next level into the Queue so we will explore those nodes next.

while(!q.isEmpty()) {
   // Create results of this level.
   List<Integer> list = new ArrayList<>();

   int size = q.size();
   for(int i = 0 ; i < size; i++) {
       Node n = q.poll();
       
       // Insert this level’s data in the list.
       list.add(n.val);

       // Add children of this level’s nodes 
       // which will be explored in the next iteration.
       q.addAll(n.children);
   }
   result.add(list);
}

Entire implementation:

public List<List<Integer>> levelOrder(Node root) {
   if (root == null) return Collections.emptyList();

   List<List<Integer>> result = new ArrayList<>();

   Deque<Node> q = new ArrayDeque<>();
   q.add(root);

   while (!q.isEmpty()) {

       // Create results of this level.
       List<Integer> list = new ArrayList<>();

       int size = q.size();
       for (int i = 0; i < size; i++) {
           Node n = q.poll();

           // Insert this level’s data in the list.
           list.add(n.val);

           // Add children of this level’s nodes 
           //which will be explored in the next iteration.
           q.addAll(n.children);
       }
       result.add(list);
   }
   return result;
}

Time and Space Complexity Nomenclature: n is the total number of nodes in a tree

Time Complexity:

1. O(n). We explore every node, hence the time complexity is O(n).

Space Complexity:

1. O(n). We save every node on the result List, hence the space complexity is O(n).

4. Conclusion

In this article, we saw how to implement Breadth First Search or BFS, i.e. level order traversal of a N-Ary tree.

GitHub link: https://github.com/savanibharat/justamonad-tutorials/blob/master/justamonad-tutorials-leetcode/src/main/java/com/justamonad/tutorials/leetcode/tree/NAryTreeLevelOrderTraversal.java 

You can read about Binary Tree Traversals (DFS and BFS) here. https://justamonad.com/binary-tree-traversals/