Given a generic tree, perform a Level order traversal and print all of its nodes
Examples:
Input : 10
/ / \ \
2 34 56 100
/ \ | / | \
77 88 1 7 8 9
Output : 10
2 34 56 100
77 88 1 7 8 9
Input : 1
/ / \ \
2 3 4 5
/ \ | / | \
6 7 8 9 10 11
Output : 1
2 3 4 5
6 7 8 9 10 11
The approach to this problem is similar to Level Order traversal in a binary tree. We Start with pushing root node in a queue and for each node we pop it, print it and push all its child in the queue.
In case of a generic tree we store child nodes in a vector. Thus we put all elements of the vector in the queue.
Implementation:
C++
// CPP program to do level order traversal// of a generic tree#include <bits/stdc++.h>using namespace std; // Represents a node of an n-ary treestruct Node{ int key; vector<Node *>child;}; // Utility function to create a new tree nodeNode *newNode(int key){ Node *temp = new Node; temp->key = key; return temp;}// Prints the n-ary tree level wisevoid LevelOrderTraversal(Node * root){ if (root==NULL) return; // Standard level order traversal code // using queue queue<Node *> q; // Create a queue q.push(root); // Enqueue root while (!q.empty()) { int n = q.size(); // If this node has children while (n > 0) { // Dequeue an item from queue and print it Node * p = q.front(); q.pop(); cout << p->key << " "; // Enqueue all children of the dequeued item for (int i=0; i<p->child.size(); i++) q.push(p->child[i]); n--; } cout << endl; // Print new line between two levels }} // Driver programint main(){ /* Let us create below tree * 10 * / / \ \ * 2 34 56 100 * / \ | / | \ * 77 88 1 7 8 9 */ Node *root = newNode(10); (root->child).push_back(newNode(2)); (root->child).push_back(newNode(34)); (root->child).push_back(newNode(56)); (root->child).push_back(newNode(100)); (root->child[0]->child).push_back(newNode(77)); (root->child[0]->child).push_back(newNode(88)); (root->child[2]->child).push_back(newNode(1)); (root->child[3]->child).push_back(newNode(7)); (root->child[3]->child).push_back(newNode(8)); (root->child[3]->child).push_back(newNode(9)); cout << "Level order traversal Before Mirroring\n"; LevelOrderTraversal(root); return 0;} |
Java
// Java program to do level order traversal// of a generic treeimport java.util.*;class GFG {// Represents a node of an n-ary treestatic class Node{ int key; Vector<Node >child = new Vector<>();};// Utility function to create a new tree nodestatic Node newNode(int key){ Node temp = new Node(); temp.key = key; return temp;}// Prints the n-ary tree level wisestatic void LevelOrderTraversal(Node root){ if (root == null) return; // Standard level order traversal code // using queue Queue<Node > q = new LinkedList<>(); // Create a queue q.add(root); // Enqueue root while (!q.isEmpty()) { int n = q.size(); // If this node has children while (n > 0) { // Dequeue an item from queue // and print it Node p = q.peek(); q.remove(); System.out.print(p.key + " "); // Enqueue all children of // the dequeued item for (int i = 0; i < p.child.size(); i++) q.add(p.child.get(i)); n--; } // Print new line between two levels System.out.println(); }}// Driver Codepublic static void main(String[] args) { /* Let us create below tree * 10 * / / \ \ * 2 34 56 100 * / \ | / | \ * 77 88 1 7 8 9 */ Node root = newNode(10); (root.child).add(newNode(2)); (root.child).add(newNode(34)); (root.child).add(newNode(56)); (root.child).add(newNode(100)); (root.child.get(0).child).add(newNode(77)); (root.child.get(0).child).add(newNode(88)); (root.child.get(2).child).add(newNode(1)); (root.child.get(3).child).add(newNode(7)); (root.child.get(3).child).add(newNode(8)); (root.child.get(3).child).add(newNode(9)); System.out.println("Level order traversal " + "Before Mirroring "); LevelOrderTraversal(root);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program to do level order traversal# of a generic tree # Represents a node of an n-ary treeclass 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 levels # Driver programif __name__=='__main__': ''' Let us create below tree 10 / / \ \ 2 34 56 100 / \ | / | \ 77 88 1 7 8 9 ''' root = newNode(10); (root.child).append(newNode(2)); (root.child).append(newNode(34)); (root.child).append(newNode(56)); (root.child).append(newNode(100)); (root.child[0].child).append(newNode(77)); (root.child[0].child).append(newNode(88)); (root.child[2].child).append(newNode(1)); (root.child[3].child).append(newNode(7)); (root.child[3].child).append(newNode(8)); (root.child[3].child).append(newNode(9)); print("Level order traversal Before Mirroring") LevelOrderTraversal(root); # This code is contributed by rutvik_56. |
C#
// C# program to do level order traversal// of a generic treeusing System;using System.Collections.Generic;class GFG {// Represents a node of an n-ary treepublic class Node{ public int key; public List<Node >child = new List<Node>();};// Utility function to create a new tree nodestatic Node newNode(int key){ Node temp = new Node(); temp.key = key; return temp;}// Prints the n-ary tree level wisestatic void LevelOrderTraversal(Node root){ if (root == null) return; // Standard level order traversal code // using queue Queue<Node > q = new Queue<Node >(); // Create a queue q.Enqueue(root); // Enqueue root while (q.Count != 0) { int n = q.Count; // If this node has children while (n > 0) { // Dequeue an item from queue // and print it Node p = q.Peek(); q.Dequeue(); Console.Write(p.key + " "); // Enqueue all children of // the dequeued item for (int i = 0; i < p.child.Count; i++) q.Enqueue(p.child[i]); n--; } // Print new line between two levels Console.WriteLine(); }}// Driver Codepublic static void Main(String[] args) { /* Let us create below tree * 10 * / / \ \ * 2 34 56 100 * / \ | / | \ * 77 88 1 7 8 9 */ Node root = newNode(10); (root.child).Add(newNode(2)); (root.child).Add(newNode(34)); (root.child).Add(newNode(56)); (root.child).Add(newNode(100)); (root.child[0].child).Add(newNode(77)); (root.child[0].child).Add(newNode(88)); (root.child[2].child).Add(newNode(1)); (root.child[3].child).Add(newNode(7)); (root.child[3].child).Add(newNode(8)); (root.child[3].child).Add(newNode(9)); Console.WriteLine("Level order traversal " + "Before Mirroring "); LevelOrderTraversal(root);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript program to do level order traversal// of a generic tree// Represents a node of an n-ary treeclass Node{ constructor() { this.key = 0; this.child = []; }};// Utility function to create a new tree nodefunction newNode(key){ var temp = new Node(); temp.key = key; return temp;}// Prints the n-ary tree level wisefunction LevelOrderTraversal(root){ if (root == null) return; // Standard level order traversal code // using queue var q = []; // Create a queue q.push(root); // push root while (q.length != 0) { var n = q.length; // If this node has children while (n > 0) { // Dequeue an item from queue // and print it var p = q[0]; q.shift(); document.write(p.key + " "); // push all children of // the dequeued item for (var i = 0; i < p.child.length; i++) q.push(p.child[i]); n--; } // Print new line between two levels document.write("<br>"); }}// Driver Code/* Let us create below tree* 10* / / \ \* 2 34 56 100* / \ | / | \* 77 88 1 7 8 9*/var root = newNode(10);(root.child).push(newNode(2));(root.child).push(newNode(34));(root.child).push(newNode(56));(root.child).push(newNode(100));(root.child[0].child).push(newNode(77));(root.child[0].child).push(newNode(88));(root.child[2].child).push(newNode(1));(root.child[3].child).push(newNode(7));(root.child[3].child).push(newNode(8));(root.child[3].child).push(newNode(9));document.write("Level order traversal " + "Before Mirroring <br>");LevelOrderTraversal(root);</script> |
Output
Level order traversal Before Mirroring 10 2 34 56 100 77 88 1 7 8 9
Time Complexity: O(n) where n is the number of nodes in the n-ary tree.
Auxiliary Space: O(n)
This article is contributed by Raghav Sharma. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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!
