### 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<Node> queue = new LinkedList<Node>(); 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(); tmp.add(curr.val); for(int j=0; j<curr.children.size();j++){ queue.offer(curr.children.get(j)); } } list.add(tmp); } return list; } }

**Other Posts You May Like**

- Introduction to N-ary Tree
- Preorder Traversal of N-ary Tree
- Postorder Traversal of N-ary Tree
- Introduction to Binary Search Tree
- Introduction to Binary Tree

## Comments

## Post a Comment