General Tree (Each node can have arbitrary number of children) Level Order Traversal

Last Updated : 14 Mar, 2023

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 tree struct Node {  int key;  vector<Node *>child; };    // Utility function to create a new tree node Node *newNode(int key) {  Node *temp = new Node;  temp->key = key;  return temp; } // Prints the n-ary tree level wise void 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 program int 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 tree import java.util.*; class GFG  { // Represents a node of an n-ary tree static class Node {  int key;  Vector<Node >child = new Vector<>(); }; // Utility function to create a new tree node static Node newNode(int key) {  Node temp = new Node();  temp.key = key;  return temp; } // Prints the n-ary tree level wise static 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 Code public 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 tree 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 # Driver program if __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# program to do level order traversal // of a generic tree using System; using System.Collections.Generic; class GFG  { // Represents a node of an n-ary tree public class Node {  public int key;  public List<Node >child = new List<Node>(); }; // Utility function to create a new tree node static Node newNode(int key) {  Node temp = new Node();  temp.key = key;  return temp; } // Prints the n-ary tree level wise static 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 Code public 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 tree class Node {  constructor()  {  this.key = 0;  this.child = [];  } }; // Utility function to create a new tree node function newNode(key) {  var temp = new Node();  temp.key = key;  return temp; } // Prints the n-ary tree level wise function 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)

Raghav Sharma 5

Article Tags :

General Tree (Each node can have arbitrary number of children) Level Order Traversal

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem

My Profile

Thank You!

What kind of Experience do you want to share?