Level order traversal of n-ary tree
Here given code implementation process.
import java.util.Vector;
import java.util.ArrayList;
// Java program for
// Iterative Level Order Traversal of an N-ary Tree
class TreeNode
{
public int key;
public Vector < TreeNode > child;
public TreeNode(int key)
{
// Set node key
this.key = key;
// Create memory of TreeNode child
this.child = new Vector < TreeNode > ();
}
public void addChild(int key)
{
// Create a new node
TreeNode node = new TreeNode(key);
// Add node into child
this.child.add(node); }
}
class QNode
{
public TreeNode node;
public QNode next;
public QNode(TreeNode node)
{
this.node = node;
this.next = null;
}
}
// Define custom queue class
class MyQueue
{
public QNode front;
public QNode rear;
public int size;
public MyQueue()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
public void enqueue(TreeNode n)
{
QNode node = new QNode(n);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear.next = node;
}
this.size++;
this.rear = node;
}
// Delete front node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size--;
}
}
public int isSize()
{
return this.size;
}
public boolean isEmpty()
{
if (this.isSize() == 0)
{
return true;
}
return false;
}
public TreeNode peek()
{
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front.node;
}
}
}
public class NAryTree
{
public TreeNode root;
public NAryTree()
{
// Set initial tree root to null
this.root = null;
}
public void printLevelOrder()
{
if(this.root == null)
{
return;
}
MyQueue record = new MyQueue();
// Add first node
record.enqueue(this.root);
TreeNode node = null;
while(record.isEmpty() == false)
{
// Get front node
node = record.peek();
// Remove front node
record.dequeue();
// Display node value
System.out.print(" "+node.key);
for (int i = 0; i < node.child.size() ; ++i)
{
// Collect child node
record.enqueue(node.child.get(i));
}
}
}
public static void main(String[] args)
{
NAryTree tree = new NAryTree();
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 2 1 3
/ \ |
17 12 15
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree.root = new TreeNode(10);
tree.root.addChild(8);
tree.root.addChild(5);
// Add child node [-2,1,6] in node (8)
tree.root.child.get(0).addChild(-2);
tree.root.child.get(0).addChild(1);
tree.root.child.get(0).addChild(6);
// Add child node [9,11] in node (1)
tree.root.child.get(0).child.get(1).addChild(9);
tree.root.child.get(0).child.get(1).addChild(11);
// Add child node [17 12] in node (11)
tree.root.child.get(0).child.get(1).child.get(1).addChild(17);
tree.root.child.get(0).child.get(1).child.get(1).addChild(12);
// Add child node [7 18 3 4] in node (5)
tree.root.child.get(1).addChild(7);
tree.root.child.get(1).addChild(18);
tree.root.child.get(1).addChild(3);
tree.root.child.get(1).addChild(4);
// Add child node [2,1,3] in node (4)
tree.root.child.get(1).child.get(3).addChild(2);
tree.root.child.get(1).child.get(3).addChild(1);
tree.root.child.get(1).child.get(3).addChild(3);
// Add child node [15] in node (1)
tree.root.child.get(1).child.get(3).child.get(1).addChild(15);
tree.printLevelOrder();
}
}
Output
10 8 5 -2 1 6 7 18 3 4 9 11 2 1 3 17 12 15
package main
import "fmt"
// Go program for
// Iterative Level Order Traversal of an N-ary Tree
type TreeNode struct {
key int
child [] *TreeNode
}
func getTreeNode(key int) * TreeNode {
var me *TreeNode = &TreeNode {}
// Set node key
me.key = key
// Create memory of TreeNode child
me.child = make([] *TreeNode,0)
return me
}
func(this *TreeNode) addChild(key int) {
// Create a new node
var node * TreeNode = getTreeNode(key)
// Add node into child
this.child = append(this.child, node)
}
type QNode struct {
node * TreeNode
next * QNode
}
func getQNode(node * TreeNode) * QNode {
var me *QNode = &QNode {}
me.node = node
me.next = nil
return me
}
// Define custom queue class
type MyQueue struct {
front * QNode
rear * QNode
size int
}
func getMyQueue() * MyQueue {
var me *MyQueue = &MyQueue {}
me.front = nil
me.rear = nil
me.size = 0
return me
}
// Add a new node at last of queue
func(this *MyQueue) enqueue(n * TreeNode) {
var node * QNode = getQNode(n)
if this.front == nil {
// When first node of queue
this.front = node
} else {
// Add node at last level
this.rear.next = node
}
this.size++
this.rear = node
}
// Delete front node of queue
func(this *MyQueue) dequeue() {
if this.front != nil {
if this.rear == this.front {
this.rear = nil
this.front = nil
} else {
this.front = this.front.next
}
this.size--
}
}
func(this MyQueue) isSize() int {
return this.size
}
func(this MyQueue) isEmpty() bool {
if this.isSize() == 0 {
return true
}
return false
}
func(this MyQueue) peek() * TreeNode {
if this.isSize() == 0 {
return nil
} else {
return this.front.node
}
}
type NAryTree struct {
root * TreeNode
}
func getNAryTree() * NAryTree {
var me *NAryTree = &NAryTree {}
// Set initial tree root to null
me.root = nil
return me
}
func(this NAryTree) printLevelOrder() {
if this.root == nil {
return
}
var record * MyQueue = getMyQueue()
// Add first node
record.enqueue(this.root)
var node * TreeNode = nil
for (record.isEmpty() == false) {
// Get front node
node = record.peek()
// Remove front node
record.dequeue()
// Display node value
fmt.Print(" ", node.key)
for i := 0 ; i < len(node.child) ; i++ {
// Collect child node
record.enqueue(node.child[i])
}
}
}
func main() {
var tree * NAryTree = getNAryTree()
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 2 1 3
/ \ |
17 12 15
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree.root = getTreeNode(10)
tree.root.addChild(8)
tree.root.addChild(5)
// Add child node [-2,1,6] in node (8)
tree.root.child[0].addChild(-2)
tree.root.child[0].addChild(1)
tree.root.child[0].addChild(6)
// Add child node [9,11] in node (1)
tree.root.child[0].child[1].addChild(9)
tree.root.child[0].child[1].addChild(11)
// Add child node [17 12] in node (11)
tree.root.child[0].child[1].child[1].addChild(17)
tree.root.child[0].child[1].child[1].addChild(12)
// Add child node [7 18 3 4] in node (5)
tree.root.child[1].addChild(7)
tree.root.child[1].addChild(18)
tree.root.child[1].addChild(3)
tree.root.child[1].addChild(4)
// Add child node [2,1,3] in node (4)
tree.root.child[1].child[3].addChild(2)
tree.root.child[1].child[3].addChild(1)
tree.root.child[1].child[3].addChild(3)
// Add child node [15] in node (1)
tree.root.child[1].child[3].child[1].addChild(15)
tree.printLevelOrder()
}
Output
10 8 5 -2 1 6 7 18 3 4 9 11 2 1 3 17 12 15
// Include header file
#include <iostream>
#include <vector>
using namespace std;
// C++ program for
// Iterative Level Order Traversal of an N-ary Tree
class TreeNode
{
public: int key;
vector < TreeNode *> child;
TreeNode(int key)
{
// Set node key
this->key = key;
}
void addChild(int key)
{
// Create a new node
TreeNode *node = new TreeNode(key);
// Add node into child
this->child.push_back(node);
}
};
class QNode
{
public:
TreeNode *node;
QNode *next;
QNode(TreeNode *node)
{
this->node = node;
this->next = NULL;
}
};
// Define custom queue class
class MyQueue
{
public: QNode *front;
QNode *rear;
int size;
MyQueue()
{
this->front = NULL;
this->rear = NULL;
this->size = 0;
}
// Add a new node at last of queue
void enqueue(TreeNode *n)
{
QNode *node = new QNode(n);
if (this->front == NULL)
{
// When first node of queue
this->front = node;
}
else
{
// Add node at last level
this->rear->next = node;
}
this->size++;
this->rear = node;
}
// Delete front node of queue
void dequeue()
{
if (this->front != NULL)
{
if (this->rear == this->front)
{
this->rear = NULL;
this->front = NULL;
}
else
{
this->front = this->front->next;
}
this->size--;
}
}
int isSize()
{
return this->size;
}
bool isEmpty()
{
if (this->isSize() == 0)
{
return true;
}
return false;
}
TreeNode *peek()
{
if (this->isSize() == 0)
{
return NULL;
}
else
{
return this->front->node;
}
}
};
class NAryTree
{
public: TreeNode *root;
NAryTree()
{
this->root = NULL;
}
void printLevelOrder()
{
if (this->root == NULL)
{
return;
}
MyQueue *record = new MyQueue();
// Add first node
record->enqueue(this->root);
TreeNode *node = NULL;
while (record->isEmpty() == false)
{
// Get front node
node = record->peek();
// Remove front node
record->dequeue();
// Display node value
cout << " " << node->key;
for (int i = 0; i < node->child.size(); ++i)
{
// Collect child node
record->enqueue(node->child.at(i));
}
}
}
};
int main()
{
NAryTree *tree = new NAryTree();
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 2 1 3
/ \ |
17 12 15
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree->root = new TreeNode(10);
tree->root->addChild(8);
tree->root->addChild(5);
// Add child node [-2,1,6] in node (8)
tree->root->child.at(0)->addChild(-2);
tree->root->child.at(0)->addChild(1);
tree->root->child.at(0)->addChild(6);
// Add child node [9,11] in node (1)
tree->root->child.at(0)->child.at(1)->addChild(9);
tree->root->child.at(0)->child.at(1)->addChild(11);
// Add child node [17 12] in node (11)
tree->root->child.at(0)->child.at(1)->child.at(1)->addChild(17);
tree->root->child.at(0)->child.at(1)->child.at(1)->addChild(12);
// Add child node [7 18 3 4] in node (5)
tree->root->child.at(1)->addChild(7);
tree->root->child.at(1)->addChild(18);
tree->root->child.at(1)->addChild(3);
tree->root->child.at(1)->addChild(4);
// Add child node [2,1,3] in node (4)
tree->root->child.at(1)->child.at(3)->addChild(2);
tree->root->child.at(1)->child.at(3)->addChild(1);
tree->root->child.at(1)->child.at(3)->addChild(3);
// Add child node [15] in node (1)
tree->root->child.at(1)->child.at(3)->child.at(1)->addChild(15);
tree->printLevelOrder();
return 0;
}
Output
10 8 5 -2 1 6 7 18 3 4 9 11 2 1 3 17 12 15
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Iterative Level Order Traversal of an N-ary Tree
public class TreeNode
{
public int key;
public List < TreeNode > child;
public TreeNode(int key)
{
// Set node key
this.key = key;
// Create memory of TreeNode child
this.child = new List < TreeNode > ();
}
public void addChild(int key)
{
// Create a new node
TreeNode node = new TreeNode(key);
// Add node into child
this.child.Add(node);
}
}
public class QNode
{
public TreeNode node;
public QNode next;
public QNode(TreeNode node)
{
this.node = node;
this.next = null;
}
}
// Define custom queue class
public class MyQueue
{
public QNode front;
public QNode rear;
public int size;
public MyQueue()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
public void enqueue(TreeNode n)
{
QNode node = new QNode(n);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear.next = node;
}
this.size++;
this.rear = node;
}
// Delete front node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size--;
}
}
public int isSize()
{
return this.size;
}
public Boolean isEmpty()
{
if (this.isSize() == 0)
{
return true;
}
return false;
}
public TreeNode peek()
{
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front.node;
}
}
}
public class NAryTree
{
public TreeNode root;
public NAryTree()
{
// Set initial tree root to null
this.root = null;
}
public void printLevelOrder()
{
if (this.root == null)
{
return;
}
MyQueue record = new MyQueue();
// Add first node
record.enqueue(this.root);
TreeNode node = null;
while (record.isEmpty() == false)
{
// Get front node
node = record.peek();
// Remove front node
record.dequeue();
// Display node value
Console.Write(" " + node.key);
for (int i = 0; i < node.child.Count; ++i)
{
// Collect child node
record.enqueue(node.child[i]);
}
}
}
public static void Main(String[] args)
{
NAryTree tree = new NAryTree();
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 2 1 3
/ \ |
17 12 15
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree.root = new TreeNode(10);
tree.root.addChild(8);
tree.root.addChild(5);
// Add child node [-2,1,6] in node (8)
tree.root.child[0].addChild(-2);
tree.root.child[0].addChild(1);
tree.root.child[0].addChild(6);
// Add child node [9,11] in node (1)
tree.root.child[0].child[1].addChild(9);
tree.root.child[0].child[1].addChild(11);
// Add child node [17 12] in node (11)
tree.root.child[0].child[1].child[1].addChild(17);
tree.root.child[0].child[1].child[1].addChild(12);
// Add child node [7 18 3 4] in node (5)
tree.root.child[1].addChild(7);
tree.root.child[1].addChild(18);
tree.root.child[1].addChild(3);
tree.root.child[1].addChild(4);
// Add child node [2,1,3] in node (4)
tree.root.child[1].child[3].addChild(2);
tree.root.child[1].child[3].addChild(1);
tree.root.child[1].child[3].addChild(3);
// Add child node [15] in node (1)
tree.root.child[1].child[3].child[1].addChild(15);
tree.printLevelOrder();
}
}
Output
10 8 5 -2 1 6 7 18 3 4 9 11 2 1 3 17 12 15
<?php
// Php program for
// Iterative Level Order Traversal of an N-ary Tree
class TreeNode
{
public $key;
public $child;
public function __construct($key)
{
// Set node key
$this->key = $key;
// Create memory of TreeNode child
$this->child = array();
}
public function addChild($key)
{
// Create a new node
$node = new TreeNode($key);
// Add node into child
$this->child[] = $node;
}
}
class QNode
{
public $node;
public $next;
public function __construct($node)
{
$this->node = $node;
$this->next = NULL;
}
}
// Define custom queue class
class MyQueue
{
public $front;
public $rear;
public $size;
public function __construct()
{
$this->front = NULL;
$this->rear = NULL;
$this->size = 0;
}
// Add a new node at last of queue
public function enqueue($n)
{
$node = new QNode($n);
if ($this->front == NULL)
{
// When first node of queue
$this->front = $node;
}
else
{
// Add node at last level
$this->rear->next = $node;
}
$this->size++;
$this->rear = $node;
}
// Delete front node of queue
public function dequeue()
{
if ($this->front != NULL)
{
if ($this->rear == $this->front)
{
$this->rear = NULL;
$this->front = NULL;
}
else
{
$this->front = $this->front->next;
}
$this->size--;
}
}
public function isSize()
{
return $this->size;
}
public function isEmpty()
{
if ($this->isSize() == 0)
{
return true;
}
return false;
}
public function peek()
{
if ($this->isSize() == 0)
{
return NULL;
}
else
{
return $this->front->node;
}
}
}
class NAryTree
{
public $root;
public function __construct()
{
$this->root = NULL;
}
public function printLevelOrder()
{
if ($this->root == NULL)
{
return;
}
$record = new MyQueue();
// Add first node
$record->enqueue($this->root);
$node = NULL;
while ($record->isEmpty() == false)
{
// Get front node
$node = $record->peek();
// Remove front node
$record->dequeue();
// Display node value
echo(" ".$node->key);
for ($i = 0; $i < count($node->child); ++$i)
{
// Collect child node
$record->enqueue($node->child[$i]);
}
}
}
}
function main()
{
$tree = new NAryTree();
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 2 1 3
/ \ |
17 12 15
-----------------------
Constructing N-Arr tree
*/
// First element of tree
$tree->root = new TreeNode(10);
$tree->root->addChild(8);
$tree->root->addChild(5);
// Add child node [-2,1,6] in node (8)
$tree->root->child[0]->addChild(-2);
$tree->root->child[0]->addChild(1);
$tree->root->child[0]->addChild(6);
// Add child node [9,11] in node (1)
$tree->root->child[0]->child[1]->addChild(9);
$tree->root->child[0]->child[1]->addChild(11);
// Add child node [17 12] in node (11)
$tree->root->child[0]->child[1]->child[1]->addChild(17);
$tree->root->child[0]->child[1]->child[1]->addChild(12);
// Add child node [7 18 3 4] in node (5)
$tree->root->child[1]->addChild(7);
$tree->root->child[1]->addChild(18);
$tree->root->child[1]->addChild(3);
$tree->root->child[1]->addChild(4);
// Add child node [2,1,3] in node (4)
$tree->root->child[1]->child[3]->addChild(2);
$tree->root->child[1]->child[3]->addChild(1);
$tree->root->child[1]->child[3]->addChild(3);
// Add child node [15] in node (1)
$tree->root->child[1]->child[3]->child[1]->addChild(15);
$tree->printLevelOrder();
}
main();
Output
10 8 5 -2 1 6 7 18 3 4 9 11 2 1 3 17 12 15
// Node JS program for
// Iterative Level Order Traversal of an N-ary Tree
class TreeNode
{
constructor(key)
{
// Set node key
this.key = key;
// Create memory of TreeNode child
this.child = [];
}
addChild(key)
{
// Create a new node
var node = new TreeNode(key);
// Add node into child
this.child.push(node);
}
}
class QNode
{
constructor(node)
{
this.node = node;
this.next = null;
}
}
// Define custom queue class
class MyQueue
{
constructor()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
enqueue(n)
{
var node = new QNode(n);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear.next = node;
}
this.size++;
this.rear = node;
}
// Delete front node of queue
dequeue()
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size--;
}
}
isSize()
{
return this.size;
}
isEmpty()
{
if (this.isSize() == 0)
{
return true;
}
return false;
}
peek()
{
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front.node;
}
}
}
class NAryTree
{
constructor()
{
this.root = null;
}
printLevelOrder()
{
if (this.root == null)
{
return;
}
var record = new MyQueue();
// Add first node
record.enqueue(this.root);
var node = null;
while (record.isEmpty() == false)
{
// Get front node
node = record.peek();
// Remove front node
record.dequeue();
// Display node value
process.stdout.write(" " + node.key);
for (var i = 0; i < node.child.length; ++i)
{
// Collect child node
record.enqueue(node.child[i]);
}
}
}
}
function main()
{
var tree = new NAryTree();
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 2 1 3
/ \ |
17 12 15
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree.root = new TreeNode(10);
tree.root.addChild(8);
tree.root.addChild(5);
// Add child node [-2,1,6] in node (8)
tree.root.child[0].addChild(-2);
tree.root.child[0].addChild(1);
tree.root.child[0].addChild(6);
// Add child node [9,11] in node (1)
tree.root.child[0].child[1].addChild(9);
tree.root.child[0].child[1].addChild(11);
// Add child node [17 12] in node (11)
tree.root.child[0].child[1].child[1].addChild(17);
tree.root.child[0].child[1].child[1].addChild(12);
// Add child node [7 18 3 4] in node (5)
tree.root.child[1].addChild(7);
tree.root.child[1].addChild(18);
tree.root.child[1].addChild(3);
tree.root.child[1].addChild(4);
// Add child node [2,1,3] in node (4)
tree.root.child[1].child[3].addChild(2);
tree.root.child[1].child[3].addChild(1);
tree.root.child[1].child[3].addChild(3);
// Add child node [15] in node (1)
tree.root.child[1].child[3].child[1].addChild(15);
tree.printLevelOrder();
}
main();
Output
10 8 5 -2 1 6 7 18 3 4 9 11 2 1 3 17 12 15
# Python 3 program for
# Iterative Level Order Traversal of an N-ary Tree
class TreeNode :
def __init__(self, key) :
# Set node key
self.key = key
# Create memory of TreeNode child
self.child = []
def addChild(self, key) :
# Create a new node
node = TreeNode(key)
# Add node into child
self.child.append(node)
class QNode :
def __init__(self, node) :
self.node = node
self.next = None
# Define custom queue class
class MyQueue :
def __init__(self) :
self.front = None
self.rear = None
self.size = 0
# Add a new node at last of queue
def enqueue(self, n) :
node = QNode(n)
if (self.front == None) :
# When first node of queue
self.front = node
else :
# Add node at last level
self.rear.next = node
self.size += 1
self.rear = node
# Delete front node of queue
def dequeue(self) :
if (self.front != None) :
if (self.rear == self.front) :
self.rear = None
self.front = None
else :
self.front = self.front.next
self.size -= 1
def isSize(self) :
return self.size
def isEmpty(self) :
if (self.isSize() == 0) :
return True
return False
def peek(self) :
if (self.isSize() == 0) :
return None
else :
return self.front.node
class NAryTree :
def __init__(self) :
self.root = None
def printLevelOrder(self) :
if (self.root == None) :
return
record = MyQueue()
# Add first node
record.enqueue(self.root)
node = None
while (record.isEmpty() == False) :
# Get front node
node = record.peek()
# Remove front node
record.dequeue()
# Display node value
print(" ", node.key, end = "")
i = 0
while (i < len(node.child)) :
# Collect child node
record.enqueue(node.child[i])
i += 1
def main() :
tree = NAryTree()
# 10
# / \
# / \
# / \
# 8 5
# /|\ /|\ \
# / | \ / | \ \
# -2 1 6 7 18 3 4
# / \ /| \
# 9 11 2 1 3
# / \ |
# 17 12 15
# -----------------------
# Constructing N-Arr tree
# First element of tree
tree.root = TreeNode(10)
tree.root.addChild(8)
tree.root.addChild(5)
# Add child node [-2,1,6] in node (8)
tree.root.child[0].addChild(-2)
tree.root.child[0].addChild(1)
tree.root.child[0].addChild(6)
# Add child node [9,11] in node (1)
tree.root.child[0].child[1].addChild(9)
tree.root.child[0].child[1].addChild(11)
# Add child node [17 12] in node (11)
tree.root.child[0].child[1].child[1].addChild(17)
tree.root.child[0].child[1].child[1].addChild(12)
# Add child node [7 18 3 4] in node (5)
tree.root.child[1].addChild(7)
tree.root.child[1].addChild(18)
tree.root.child[1].addChild(3)
tree.root.child[1].addChild(4)
# Add child node [2,1,3] in node (4)
tree.root.child[1].child[3].addChild(2)
tree.root.child[1].child[3].addChild(1)
tree.root.child[1].child[3].addChild(3)
# Add child node [15] in node (1)
tree.root.child[1].child[3].child[1].addChild(15)
tree.printLevelOrder()
if __name__ == "__main__": main()
Output
10 8 5 -2 1 6 7 18 3 4 9 11 2 1 3 17 12 15
# Ruby program for
# Iterative Level Order Traversal of an N-ary Tree
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :key, :child
attr_accessor :key, :child
def initialize(key)
# Set node key
self.key = key
# Create memory of TreeNode child
self.child = []
end
def addChild(key)
# Create a new node
node = TreeNode.new(key)
# Add node into child
self.child.push(node)
end
end
class QNode
# Define the accessor and reader of class QNode
attr_reader :node, :next
attr_accessor :node, :next
def initialize(node)
self.node = node
self.next = nil
end
end
# Define custom queue class
class MyQueue
# Define the accessor and reader of class MyQueue
attr_reader :front, :rear, :size
attr_accessor :front, :rear, :size
def initialize()
self.front = nil
self.rear = nil
self.size = 0
end
# Add a new node at last of queue
def enqueue(n)
node = QNode.new(n)
if (self.front == nil)
# When first node of queue
self.front = node
else
# Add node at last level
self.rear.next = node
end
self.size += 1
self.rear = node
end
# Delete front node of queue
def dequeue()
if (self.front != nil)
if (self.rear == self.front)
self.rear = nil
self.front = nil
else
self.front = self.front.next
end
self.size -= 1
end
end
def isSize()
return self.size
end
def isEmpty()
if (self.isSize() == 0)
return true
end
return false
end
def peek()
if (self.isSize() == 0)
return nil
else
return self.front.node
end
end
end
class NAryTree
# Define the accessor and reader of class NAryTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
def printLevelOrder()
if (self.root == nil)
return
end
record = MyQueue.new()
# Add first node
record.enqueue(self.root)
node = nil
while (record.isEmpty() == false)
# Get front node
node = record.peek()
# Remove front node
record.dequeue()
# Display node value
print(" ", node.key)
i = 0
while (i < node.child.length)
# Collect child node
record.enqueue(node.child[i])
i += 1
end
end
end
end
def main()
tree = NAryTree.new()
# 10
# / \
# / \
# / \
# 8 5
# /|\ /|\ \
# / | \ / | \ \
# -2 1 6 7 18 3 4
# / \ /| \
# 9 11 2 1 3
# / \ |
# 17 12 15
# -----------------------
# Constructing N-Arr tree
# First element of tree
tree.root = TreeNode.new(10)
tree.root.addChild(8)
tree.root.addChild(5)
# Add child node [-2,1,6] in node (8)
tree.root.child[0].addChild(-2)
tree.root.child[0].addChild(1)
tree.root.child[0].addChild(6)
# Add child node [9,11] in node (1)
tree.root.child[0].child[1].addChild(9)
tree.root.child[0].child[1].addChild(11)
# Add child node [17 12] in node (11)
tree.root.child[0].child[1].child[1].addChild(17)
tree.root.child[0].child[1].child[1].addChild(12)
# Add child node [7 18 3 4] in node (5)
tree.root.child[1].addChild(7)
tree.root.child[1].addChild(18)
tree.root.child[1].addChild(3)
tree.root.child[1].addChild(4)
# Add child node [2,1,3] in node (4)
tree.root.child[1].child[3].addChild(2)
tree.root.child[1].child[3].addChild(1)
tree.root.child[1].child[3].addChild(3)
# Add child node [15] in node (1)
tree.root.child[1].child[3].child[1].addChild(15)
tree.printLevelOrder()
end
main()
Output
10 8 5 -2 1 6 7 18 3 4 9 11 2 1 3 17 12 15
import scala.collection.mutable._;
// Scala program for
// Iterative Level Order Traversal of an N-ary Tree
class TreeNode(var key: Int,
var child: ArrayBuffer[TreeNode])
{
def this(key: Int)
{
// Set node key
// Create memory of TreeNode child
this(key, new ArrayBuffer[TreeNode]());
}
def addChild(key: Int): Unit = {
// Create a new node
var node: TreeNode = new TreeNode(key);
// Add node into child
this.child += node;
}
}
class QNode(var node: TreeNode,
var next: QNode)
{
def this(node: TreeNode)
{
this(node, null);
}
}
// Define custom queue class
class MyQueue(var front: QNode,
var rear: QNode,
var size: Int)
{
def this()
{
this(null, null, 0);
}
// Add a new node at last of queue
def enqueue(n: TreeNode): Unit = {
var node: QNode = new QNode(n);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear.next = node;
}
this.size += 1;
this.rear = node;
}
// Delete front node of queue
def dequeue(): Unit = {
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size -= 1;
}
}
def isSize(): Int = {
return this.size;
}
def isEmpty(): Boolean = {
if (this.isSize() == 0)
{
return true;
}
return false;
}
def peek(): TreeNode = {
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front.node;
}
}
}
class NAryTree(var root: TreeNode)
{
def this()
{
this(null);
}
def printLevelOrder(): Unit = {
if (this.root == null)
{
return;
}
var record: MyQueue = new MyQueue();
// Add first node
record.enqueue(this.root);
var node: TreeNode = null;
while (record.isEmpty() == false)
{
// Get front node
node = record.peek();
// Remove front node
record.dequeue();
// Display node value
print(" " + node.key);
var i: Int = 0;
while (i < node.child.size)
{
// Collect child node
record.enqueue(node.child(i));
i += 1;
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: NAryTree = new NAryTree();
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 2 1 3
/ \ |
17 12 15
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree.root = new TreeNode(10);
tree.root.addChild(8);
tree.root.addChild(5);
// Add child node [-2,1,6] in node (8)
tree.root.child(0).addChild(-2);
tree.root.child(0).addChild(1);
tree.root.child(0).addChild(6);
// Add child node [9,11] in node (1)
tree.root.child(0).child(1).addChild(9);
tree.root.child(0).child(1).addChild(11);
// Add child node [17 12] in node (11)
tree.root.child(0).child(1).child(1).addChild(17);
tree.root.child(0).child(1).child(1).addChild(12);
// Add child node [7 18 3 4] in node (5)
tree.root.child(1).addChild(7);
tree.root.child(1).addChild(18);
tree.root.child(1).addChild(3);
tree.root.child(1).addChild(4);
// Add child node [2,1,3] in node (4)
tree.root.child(1).child(3).addChild(2);
tree.root.child(1).child(3).addChild(1);
tree.root.child(1).child(3).addChild(3);
// Add child node [15] in node (1)
tree.root.child(1).child(3).child(1).addChild(15);
tree.printLevelOrder();
}
}
Output
10 8 5 -2 1 6 7 18 3 4 9 11 2 1 3 17 12 15
import Foundation;
// Swift 4 program for
// Iterative Level Order Traversal of an N-ary Tree
class TreeNode
{
var key: Int;
var child: [TreeNode? ];
init(_ key: Int)
{
// Set node key
self.key = key;
// Create memory of TreeNode child
self.child = [TreeNode? ]();
}
func addChild(_ key: Int)
{
// Create a new node
let node: TreeNode = TreeNode(key);
// Add node into child
self.child.append(node);
}
}
class QNode
{
var node: TreeNode? ;
var next: QNode? ;
init(_ node: TreeNode? )
{
self.node = node;
self.next = nil;
}
}
// Define custom queue class
class MyQueue
{
var front: QNode? ;
var rear: QNode? ;
var size: Int;
init()
{
self.front = nil;
self.rear = nil;
self.size = 0;
}
// Add a new node at last of queue
func enqueue(_ n: TreeNode? )
{
let node: QNode = QNode(n);
if (self.front == nil)
{
// When first node of queue
self.front = node;
}
else
{
// Add node at last level
self.rear!.next = node;
}
self.size += 1;
self.rear = node;
}
// Delete front node of queue
func dequeue()
{
if (self.front != nil)
{
if (self.rear === self.front)
{
self.rear = nil;
self.front = nil;
}
else
{
self.front = self.front!.next;
}
self.size -= 1;
}
}
func isSize() -> Int
{
return self.size;
}
func isEmpty() -> Bool
{
if (self.isSize() == 0)
{
return true;
}
return false;
}
func peek() -> TreeNode?
{
if (self.isSize() == 0)
{
return nil;
}
else
{
return self.front!.node;
}
}
}
class NAryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
func printLevelOrder()
{
if (self.root == nil)
{
return;
}
let record: MyQueue = MyQueue();
// Add first node
record.enqueue(self.root);
var node: TreeNode? = nil;
while (record.isEmpty() == false)
{
// Get front node
node = record.peek();
// Remove front node
record.dequeue();
// Display node value
print(" ", node!.key, terminator: "");
var i: Int = 0;
while (i < node!.child.count)
{
// Collect child node
record.enqueue(node!.child[i]);
i += 1;
}
}
}
}
func main()
{
let tree: NAryTree = NAryTree();
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 2 1 3
/ \ |
17 12 15
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree.root = TreeNode(10);
tree.root!.addChild(8);
tree.root!.addChild(5);
// Add child node [-2,1,6] in node (8)
tree.root!.child[0]!.addChild(-2);
tree.root!.child[0]!.addChild(1);
tree.root!.child[0]!.addChild(6);
// Add child node [9,11] in node (1)
tree.root!.child[0]!.child[1]!.addChild(9);
tree.root!.child[0]!.child[1]!.addChild(11);
// Add child node [17 12] in node (11)
tree.root!.child[0]!.child[1]!.child[1]!.addChild(17);
tree.root!.child[0]!.child[1]!.child[1]!.addChild(12);
// Add child node [7 18 3 4] in node (5)
tree.root!.child[1]!.addChild(7);
tree.root!.child[1]!.addChild(18);
tree.root!.child[1]!.addChild(3);
tree.root!.child[1]!.addChild(4);
// Add child node [2,1,3] in node (4)
tree.root!.child[1]!.child[3]!.addChild(2);
tree.root!.child[1]!.child[3]!.addChild(1);
tree.root!.child[1]!.child[3]!.addChild(3);
// Add child node [15] in node (1)
tree.root!.child[1]!.child[3]!.child[1]!.addChild(15);
tree.printLevelOrder();
}
main();
Output
10 8 5 -2 1 6 7 18 3 4 9 11 2 1 3 17 12 15
// Kotlin program for
// Iterative Level Order Traversal of an N-ary Tree
class TreeNode
{
var key: Int;
var child: MutableList < TreeNode > ;
constructor(key: Int)
{
// Set node key
this.key = key;
// Create memory of TreeNode child
this.child = mutableListOf < TreeNode > ();
}
fun addChild(key: Int): Unit
{
// Create a new node
val node: TreeNode = TreeNode(key);
// Add node into child
this.child.add(node);
}
}
class QNode
{
var node: TreeNode ? ;
var next: QNode ? ;
constructor(node: TreeNode ? )
{
this.node = node;
this.next = null;
}
}
// Define custom queue class
class MyQueue
{
var front: QNode ? ;
var rear: QNode ? ;
var size: Int;
constructor()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
fun enqueue(n: TreeNode ? ): Unit
{
val node: QNode = QNode(n);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear?.next = node;
}
this.size += 1;
this.rear = node;
}
// Delete front node of queue
fun dequeue(): Unit
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front?.next;
}
this.size -= 1;
}
}
fun isSize(): Int
{
return this.size;
}
fun isEmpty(): Boolean
{
if (this.isSize() == 0)
{
return true;
}
return false;
}
fun peek(): TreeNode ?
{
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front?.node;
}
}
}
class NAryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
fun printLevelOrder(): Unit
{
if (this.root == null)
{
return;
}
val record: MyQueue = MyQueue();
// Add first node
record.enqueue(this.root);
var node: TreeNode ? ;
while (record.isEmpty() == false)
{
// Get front node
node = record.peek();
// Remove front node
record.dequeue();
// Display node value
print(" " + node!!.key);
var i: Int = 0;
while (i < node.child.size)
{
// Collect child node
record.enqueue(node.child[i]);
i += 1;
}
}
}
}
fun main(args: Array < String > ): Unit
{
val tree: NAryTree = NAryTree();
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 2 1 3
/ \ |
17 12 15
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree.root = TreeNode(10);
tree.root?.addChild(8);
tree.root?.addChild(5);
// Add child node [-2,1,6] in node (8)
tree.root!!.child[0].addChild(-2);
tree.root!!.child[0].addChild(1);
tree.root!!.child[0].addChild(6);
// Add child node [9,11] in node (1)
tree.root!!.child[0].child[1].addChild(9);
tree.root!!.child[0].child[1].addChild(11);
// Add child node [17 12] in node (11)
tree.root!!.child[0].child[1].child[1].addChild(17);
tree.root!!.child[0].child[1].child[1].addChild(12);
// Add child node [7 18 3 4] in node (5)
tree.root!!.child[1].addChild(7);
tree.root!!.child[1].addChild(18);
tree.root!!.child[1].addChild(3);
tree.root!!.child[1].addChild(4);
// Add child node [2,1,3] in node (4)
tree.root!!.child[1].child[3].addChild(2);
tree.root!!.child[1].child[3].addChild(1);
tree.root!!.child[1].child[3].addChild(3);
// Add child node [15] in node (1)
tree.root!!.child[1].child[3].child[1].addChild(15);
tree.printLevelOrder();
}
Output
10 8 5 -2 1 6 7 18 3 4 9 11 2 1 3 17 12 15
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment