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:
Image
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:
Image
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 nodeNode* newNode(int key){ Node* temp = new Node; temp->val = key; return temp;}// Function for level order traversal for n-array treevector<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 codeint 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 implementationclass Node: def __init__(self, key): self.key = key self.child = [] # Utility function to create a new tree nodedef newNode(key): temp = Node(key) return temp # Prints the n-ary tree level wisedef 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 levelsif __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 approachusing 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 implementationclass Node { constructor(val) { this.val = val; this.children = new Array(); }}// Function for level order traversal for n-array treefunction 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 codelet 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>");} |
Output
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 implementationans = []level = 0class 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 -= 1root = 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 approachusing 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 |
Output
1 3 2 4 5 6
Time Complexity: O(V)
Auxiliary Space: O(V)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
