### Level Order Traversal of N-ary Tree - The Coding Shala

Last Updated: 26-Jan-2021
Home >> Data Structures >> Level Order Traversal of N-ary Tree

In this post, we will learn how to do Level Order Traversal of N-ary Tree and will write a Java program for the level order Traversal.

## Level Order Traversal of N-ary Tree

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

For example, given a 3-ary tree:

1
/  |  \
3  2  4
/ \
5   6
We should return its level order traversal:

[
[1],
[3,2,4],
[5,6]
]

## Level Order Traversal of N-ary Tree Java Program

Approach 1

Iterative Solution, using the queue.

• step 1. insert root node to queue.
• step 2. while the queue is not empty.
• step 3. get the current queue size.
• step 4. remove the first node from the queue and add it to the list.
• step 5. add all the children of the current node to the queue.
• step 6. return list.
Java Program:

```/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;

public Node() {}

public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> list = new ArrayList<>();
if(root == null) return list;
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> tmp = new ArrayList<Integer>();
for(int i=0;i<size;i++){
Node curr = queue.poll();
for(int j=0; j<curr.children.size();j++){
queue.offer(curr.children.get(j));
}
}
}
return list;
}
}
```

Other Posts You May Like