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

Please leave a comment below if you like this post or found some errors, it will help me to improve my content.