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

Given a generic tree, perform a Level order traversal and print all of its nodes

```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
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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.

 `// CPP program to do level order traversal ` `// of a generic tree ` `#include ` `using` `namespace` `std; ` `  `  `// Represents a node of an n-ary tree ` `struct` `Node ` `{ ` `    ``int` `key; ` `    ``vectorchild; ` `}; ` `  `  ` ``// 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 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; ichild.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->child).push_back(newNode(77)); ` `    ``(root->child->child).push_back(newNode(88)); ` `    ``(root->child->child).push_back(newNode(1)); ` `    ``(root->child->child).push_back(newNode(7)); ` `    ``(root->child->child).push_back(newNode(8)); ` `    ``(root->child->child).push_back(newNode(9)); ` `  `  `    ``cout << ````"Level order traversal Before Mirroring "````; ` `    ``LevelOrderTraversal(root); ` `   `  `    ``return` `0; ` `}  `

```Output:
10
2 34 56 100
77 88 1 7 8 9

```

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

code

load comments