Level Order Traversal of N-ary Tree
Given an N-ary Tree. The task is to print the level order traversal of the tree where each level will be in a new line.
Examples:
Input:
Output:
1
3 2 4
5 6
Explanation: At level 1: only 1 is present.
At level 2: 3, 2, 4 is present
At level 3: 5, 6 is presentInput:
Output:
1
2 3 4 5
6 7 8 9 10
11 12 13
14
Explanation: For the above example there are 5 level present in the n-ary tree.
At level 1: only 1 is present.
At level 2: 2, 3, 4, 5 is present.
At level 3: 6, 7, 8, 9, 10 is present
At level 4:11, 12, 13 is present
At level 5 :- 14 is present
Approach 1: Using BFS
The approach of the problem is to use Level Order Traversal and store all the levels in a 2D array where each of the levels is stored in a different row.
Follow the below steps to implement the approach:
- Create a vector ans and temp to store the level order traversal of the N-ary tree.
- Push the root node in the queue.
- Run a while loop until the queue is not empty:
- Determine the size of the current level which is the size of the queue (say N):
- Run a loop for i = 1 to N
- In each step delete the front node (say cur) and push its data to the temp as a part of the current level.
- Push all the children of cur into the queue.
- Push the temp into the final ans vector which stores the different levels in different rows.
- Determine the size of the current level which is the size of the queue (say N):
- Return the ans vector.
Below is the implementation of the above approach:
C++
// C++ code for above implementation #include <bits/stdc++.h> using namespace std; struct Node { char val; vector<Node*> children; }; // Utility function to create a new tree node Node* newNode( int key) { Node* temp = new Node; temp->val = key; return temp; } // Function for level order traversal for n-array tree vector<vector< int > > levelOrder(Node* root) { vector<vector< int > > ans; if (!root) cout << "N-Ary tree does not any nodes" ; // Create a queue namely main_queue queue<Node*> main_queue; // Push the root value in the main_queue main_queue.push(root); // Create a temp vector to store the all the node values // present at a particular level vector< int > temp; // Run a while loop until the main_queue is empty while (!main_queue.empty()) { // Get the front of the main_queue int n = main_queue.size(); // Iterate through the current level for ( int i = 0; i < n; i++) { Node* cur = main_queue.front(); main_queue.pop(); temp.push_back(cur->val); for ( auto u : cur->children) main_queue.push(u); } ans.push_back(temp); temp.clear(); } return ans; } // Driver code int main() { Node* root = newNode(1); root->children.push_back(newNode(3)); root->children.push_back(newNode(2)); root->children.push_back(newNode(4)); root->children[0]->children.push_back(newNode(5)); root->children[0]->children.push_back(newNode(6)); // LevelOrderTraversal obj; vector<vector< int > > ans = levelOrder(root); for ( auto v : ans) { for ( int x : v) cout << x << " " ; cout << endl; } return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
Java
import java.util.*; public class Main { static class Node { public int val; public Vector<Node> children; public Node( int key) { val = key; children = new Vector<Node>(); } } // Utility function to create a new tree node static Node newNode( int key) { Node temp = new Node(key); return temp; } // Function for level order traversal for n-array tree static List<List<Integer> > levelOrder(Node root) { List<List<Integer> > ans = new ArrayList<>(); if (root == null ) System.out.println( "N-Ary tree does not any nodes" ); // Create one queue main_queue Queue<Node> main_queue = new LinkedList<>(); // Push the root value in the main_queue main_queue.offer(root); // Traverse the N-ary Tree by level while (!main_queue.isEmpty()) { // Create a temp vector to store the all the // node values present at a particular level List<Integer> temp = new ArrayList<>(); int size = main_queue.size(); // Iterate through the current level for ( int i = 0 ; i < size; i++) { Node node = main_queue.poll(); temp.add(node.val); for (Node child : node.children) { main_queue.offer(child); } } ans.add(temp); } return ans; } // Utility function to print the level order traversal public static void printList(List<List<Integer> > temp) { for (List<Integer> it : temp) { for (Integer et : it) System.out.print(et + " " ); System.out.println(); } } public static void main(String[] args) { Node root = newNode( 1 ); (root.children).add(newNode( 3 )); (root.children).add(newNode( 2 )); (root.children).add(newNode( 4 )); (root.children.get( 0 ).children).add(newNode( 5 )); (root.children.get( 0 ).children).add(newNode( 6 )); List<List<Integer> > ans = levelOrder(root); printList(ans); } } // This code is contributed by Sania Kumari Gupta |
Python3
# Python code for above implementation class Node: def __init__( self , key): self .key = key self .child = [] # Utility function to create a new tree node def newNode(key): temp = Node(key) return temp # Prints the n-ary tree level wise def LevelOrderTraversal(root): if (root = = None ): return ; # Standard level order traversal code # using queue q = [] # Create a queue q.append(root); # Enqueue root while ( len (q) ! = 0 ): n = len (q); # If this node has children while (n > 0 ): # Dequeue an item from queue and print it p = q[ 0 ] q.pop( 0 ); print (p.key, end = ' ' ) # Enqueue all children of the dequeued item for i in range ( len (p.child)): q.append(p.child[i]); n - = 1 print () # Print new line between two levels if __name__ = = '__main__' : root = newNode( 1 ); root.child.append(newNode( 3 )); root.child.append(newNode( 2 )); root.child.append(newNode( 4 )); root.child[ 0 ].child.append(newNode( 5 )); root.child[ 0 ].child.append(newNode( 6 )); # LevelOrderTraversal obj; LevelOrderTraversal(root); # This code is contributed by poojaagarwal2. |
C#
// C# code implementation for the abvoe approach using System; using System.Collections.Generic; using System.Linq; public class Node { public int val; public List<Node> children; public Node( int key) { val = key; children = new List<Node>(); } } public class GFG { // Utility function to create a new tree node static Node newNode( int key) { Node temp = new Node(key); return temp; } // Function for level order traversal for n-array tree static List<List< int > > levelOrder(Node root) { List<List< int > > ans = new List<List< int > >(); if (root == null ) Console.WriteLine( "N-Ary tree does not any nodes" ); // Create one queue main_queue Queue<Node> main_queue = new Queue<Node>(); // Push the root value in the main_queue main_queue.Enqueue(root); // Traverse the N-ary Tree by level while (main_queue.Any()) { // Create a temp vector to store the all the // node values present at a particular level List< int > temp = new List< int >(); int size = main_queue.Count; // Iterate through the current level for ( int i = 0; i < size; i++) { Node node = main_queue.Dequeue(); temp.Add(node.val); foreach (Node child in node.children) { main_queue.Enqueue(child); } } ans.Add(temp); } return ans; } // Utility function to print the level order traversal public static void printList(List<List< int > > temp) { foreach (List< int > it in temp) { foreach ( int et in it) Console.Write(et + " " ); Console.WriteLine(); } } static public void Main() { // Code Node root = newNode(1); (root.children).Add(newNode(3)); (root.children).Add(newNode(2)); (root.children).Add(newNode(4)); (root.children[0].children).Add(newNode(5)); (root.children[0].children).Add(newNode(6)); List<List< int > > ans = levelOrder(root); printList(ans); } } // This code is contributed by karthik. |
Javascript
// Javascript code for above implementation class Node { constructor(val) { this .val = val; this .children = new Array(); } } // Function for level order traversal for n-array tree function levelOrder( root) { let ans = []; if (!root) console.log( "N-Ary tree does not any nodes" ); // Create a queue namely main_queue let main_queue=[]; // Push the root value in the main_queue main_queue.push(root); // Create a temp vector to store the all the node values // present at a particular level let temp=[]; // Run a while loop until the main_queue is empty while (main_queue.length) { // Get the front of the main_queue let n = main_queue.length; // Iterate through the current level for (let i = 0; i < n; i++) { let cur = main_queue.shift(); temp.push(cur.val); for (let u of cur.children) main_queue.push(u); } ans.push(temp); temp=[]; } return ans; } // Driver code let root = new Node(1); root.children.push( new Node(3)); root.children.push( new Node(2)); root.children.push( new Node(4)); root.children[0].children.push( new Node(5)); root.children[0].children.push( new Node(6)); // LevelOrderTraversal obj; let ans = levelOrder(root); for (let v of ans) { for (let x of v) console.log(x+ " " ); console.log( "<br>" ); } |
1 3 2 4 5 6
Time Complexity: O(V) where V is the number of nodes
Auxiliary Space: O(V)
Approach 2: Using DFS
The approach of the problem is to use Level Order Traversal using DFS and store all the levels in a 2D array where each of the levels is stored in a different row.
- LevelOrder function will update ans with the current value, pushing it in with a new sub-vector if one matching the level is not present already into ans.
- Function will increase level by 1;
- It will call itself recursively on all the children;
- It will backtrack level.
Below is the implementation of the above approach:
C++
// C++ code for above implementation #include <bits/stdc++.h> using namespace std; vector<vector< int > > ans; int level = 0; struct Node { char val; vector<Node*> children; }; Node* newNode( int key) { Node* temp = new Node; temp->val = key; return temp; } void levelOrder(Node *root) { if (ans.size() == level) ans.push_back({root->val}); else ans[level].push_back(root->val); level++; for (Node *n: root->children) levelOrder(n); level--; } int main() { Node* root = newNode(1); root->children.push_back(newNode(3)); root->children.push_back(newNode(2)); root->children.push_back(newNode(4)); root->children[0]->children.push_back(newNode(5)); root->children[0]->children.push_back(newNode(6)); // LevelOrderTraversal obj; levelOrder(root); for ( auto v : ans) { for ( int x : v) cout << x << " " ; cout << endl; } return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; import java.util.*; public class GFG { static List<List<Integer> > result = new ArrayList<>(); static int level = 0 ; static class Node { public int val; public Vector<Node> children; public Node( int key) { val = key; children = new Vector<Node>(); } } // Utility function to create a new tree node static Node newNode( int key) { Node temp = new Node(key); return temp; } // method to find level order traversal of n-ary tree static void levelOrder(Node node) { if (node == null ) { return ; } List<Integer> list = result.size() > level ? result.get(level) : new ArrayList<>(); // adding node value to the list list.add(node.val); if (result.size() <= level) { result.add(list); } // promoting/incrementing the level to next level++; for (Node n : node.children) { levelOrder(n); } level--; } // utility function to print level order traversal public static void printList(List<List<Integer> > temp) { for (List<Integer> it : temp) { for (Integer et : it) System.out.print(et + " " ); System.out.println(); } } public static void main(String[] args) { Node root = newNode( 1 ); (root.children).add(newNode( 3 )); (root.children).add(newNode( 2 )); (root.children).add(newNode( 4 )); (root.children.get( 0 ).children).add(newNode( 5 )); (root.children.get( 0 ).children).add(newNode( 6 )); levelOrder(root); printList(result); } } |
Python3
# Python code for above implementation ans = [] level = 0 class Node: def __init__( self , val): self .val = val self .children = [] def levelOrder(root): global level if len (ans) = = level: ans.append([root.val]) else : ans[level].append(root.val) level + = 1 for n in root.children: levelOrder(n) level - = 1 root = Node( 1 ) root.children.append(Node( 3 )) root.children.append(Node( 2 )) root.children.append(Node( 4 )) root.children[ 0 ].children.append(Node( 5 )) root.children[ 0 ].children.append(Node( 6 )) levelOrder(root) for v in ans: for x in v: print (x, end = " " ) print () # This code is contributed by Tapesh(tapeshdua420) |
C#
// C# code for the above approach using System; using System.Collections.Generic; public class GFG { static List<List< int > > result = new List<List< int > >(); static int level = 0; public class Node { public int val; public List<Node> children; public Node( int key) { val = key; children = new List<Node>(); } } // Utility function to create a new tree node static Node newNode( int key) { Node temp = new Node(key); return temp; } // method to find level order traversal of n-ary tree static void levelOrder(Node node) { if (node == null ) { return ; } List< int > list = result.Count > level ? result[level] : new List< int >(); // adding node value to the list list.Add(node.val); if (result.Count <= level) { result.Add(list); } // promoting/incrementing the level to next level++; foreach (Node n in node.children) { levelOrder(n); } level--; } // utility function to print level order traversal public static void printList(List<List< int > > temp) { foreach (List< int > it in temp) { foreach ( int et in it) { Console.Write(et + " " ); } Console.WriteLine(); } } static public void Main() { // Code Node root = newNode(1); (root.children).Add(newNode(3)); (root.children).Add(newNode(2)); (root.children).Add(newNode(4)); (root.children[0].children).Add(newNode(5)); (root.children[0].children).Add(newNode(6)); levelOrder(root); printList(result); } } // This code is contributed by sankar. |
Javascript
// JavaScript code for the above approach const ans = []; let level = 0; class Node { constructor(val) { this .val = val; this .children = []; } } function levelOrder(root) { if (ans.length === level) ans.push([root.val]); else ans[level].push(root.val); level++; for (const n of root.children) levelOrder(n); level--; } // create tree const root = new Node(1); root.children.push( new Node(3)); root.children.push( new Node(2)); root.children.push( new Node(4)); root.children[0].children.push( new Node(5)); root.children[0].children.push( new Node(6)); levelOrder(root); for (const v of ans) { for (const x of v) { console.log(x + " " ); } console.log( '<br>' ); } // This code is contributed by Potta Lokesh |
1 3 2 4 5 6
Time Complexity: O(V)
Auxiliary Space: O(V)
Contact Us