Iterative n-ary tree preorder traversal
In the realm of N-ary trees, the iterative preorder traversal technique stands as an essential tool for navigating through their diverse structures. This article unveils the magic behind this traversal method, diving into problem elucidation, algorithmic breakdown, code implementation, and output comprehension.
Problem Statement
The task at hand involves executing a preorder traversal on an N-ary tree using an iterative approach. Preorder traversal visits the root node first, followed by traversing all the subtrees rooted at the children of the root.
Example
Consider the following N-ary tree:
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 2 1 3
/ \
17 12
Upon executing iterative preorder traversal, the nodes are printed in the sequence: 10, 8, -2, 1, 9, 11, 17, 12, 6, 5, 7, 18, 3, 4, 2, 1, and 3.
Idea to Solve
Iterative preorder traversal employs a stack to manage nodes' processing order. The algorithm simulates the recursive behavior by pushing nodes onto the stack while visiting them in the expected preorder manner.
Pseudocode
function printPreorder():
if tree root is null:
return
create an empty stack
push the root node onto the stack
while stack is not empty:
pop a node from the top of the stack
push all children of the node onto the stack (in reverse order)
print the node's valueAlgorithm Explanation
- If the root of the tree is null, return.
- Create an empty stack.
- Push the root node onto the stack.
- While the stack is not empty:
- Pop a node from the top of the stack.
- Push all children of the node onto the stack, ensuring the last child is pushed first.
- Print the value of the node.
Code Solution
import java.util.Vector;
import java.util.ArrayList;
import java.util.Stack;
// Java program for
// Iterative Preorder 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);
}
}
public class NAryTree
{
public TreeNode root;
public NAryTree()
{
// Set initial tree root to null
this.root = null;
}
public void printPreorder()
{
if (this.root == null)
{
return;
}
Stack < TreeNode > record = new Stack < TreeNode > ();
// Add first node
record.push(this.root);
TreeNode node = null;
while (record.isEmpty() == false)
{
// Get top element
node = record.peek();
// Remove top element
record.pop();
for (int i = node.child.size() - 1; i >= 0; --i)
{
record.push(node.child.get(i));
}
// Print node value
System.out.print(" " + node.key);
}
}
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
-----------------------
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);
tree.printPreorder();
}
}Output
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 1 3package main
import "fmt"
// Go program for
// Iterative Preorder 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 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) printPreorder() {
if this.root == nil {
return
}
var record = make([] *TreeNode, 0)
// Add first node
record = append(record, this.root)
var node * TreeNode = nil
for (len(record) > 0 ) {
// Get top element
node = record[len(record) - 1]
// Remove top element
record = record[: len(record) - 1]
for i := len(node.child) - 1 ; i >= 0 ; i-- {
record = append(record, node.child[i])
}
// Print node value
fmt.Print(" ", node.key)
}
}
func main() {
var tree * NAryTree = getNAryTree()
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 2 1 3
/ \
17 12
-----------------------
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)
tree.printPreorder()
}Output
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 1 3// Include header file
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
// C++ program for
// Iterative Preorder 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 NAryTree
{
public: TreeNode *root;
NAryTree()
{
this->root = NULL;
}
void printPreorder()
{
if (this->root == NULL)
{
return;
}
stack < TreeNode *> record;
// Add first node
record.push(this->root);
TreeNode *node = NULL;
while (record.empty() == false)
{
// Get top element
node = record.top();
// Remove top element
record.pop();
for (int i = node->child.size() - 1; i >= 0; --i)
{
record.push(node->child.at(i));
}
// Print node value
cout << " " << node->key;
}
}
};
int main()
{
NAryTree *tree = new NAryTree();
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 2 1 3
/ \
17 12
-----------------------
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);
tree->printPreorder();
return 0;
}Output
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 1 3// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Iterative Preorder 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 NAryTree
{
public TreeNode root;
public NAryTree()
{
// Set initial tree root to null
this.root = null;
}
public void printPreorder()
{
if (this.root == null)
{
return;
}
Stack < TreeNode > record = new Stack < TreeNode > ();
// Add first node
record.Push(this.root);
TreeNode node = null;
while ((record.Count == 0) == false)
{
// Get top element
node = record.Peek();
// Remove top element
record.Pop();
for (int i = node.child.Count - 1; i >= 0; --i)
{
record.Push(node.child[i]);
}
// Print node value
Console.Write(" " + node.key);
}
}
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
-----------------------
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);
tree.printPreorder();
}
}Output
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 1 3<?php
// Php program for
// Iterative Preorder 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 NAryTree
{
public $root;
public function __construct()
{
$this->root = NULL;
}
public function printPreorder()
{
if ($this->root == NULL)
{
return;
}
$record = array();
// Add first node
array_push($record, $this->root);
$node = NULL;
while (empty($record) == false)
{
// Get top element
$node = end($record);
// Remove top element
array_pop($record);
for ($i = count($node->child) - 1; $i >= 0; --$i)
{
array_push($record, $node->child[$i]);
}
// Print node value
echo(" ".$node->key);
}
}
}
function main()
{
$tree = new NAryTree();
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 2 1 3
/ \
17 12
-----------------------
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);
$tree->printPreorder();
}
main();Output
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 1 3// Node JS program for
// Iterative Preorder 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 NAryTree
{
constructor()
{
this.root = null;
}
printPreorder()
{
if (this.root == null)
{
return;
}
var record = [];
// Add first node
record.push(this.root);
var node = null;
while ((record.length == 0) == false)
{
// Get top element
node = record[record.length - 1];
// Remove top element
record.pop();
for (var i = node.child.length - 1; i >= 0; --i)
{
record.push(node.child[i]);
}
// Print node value
process.stdout.write(" " + node.key);
}
}
}
function main()
{
var tree = new NAryTree();
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 2 1 3
/ \
17 12
-----------------------
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);
tree.printPreorder();
}
main();Output
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 1 3# Python 3 program for
# Iterative Preorder 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 NAryTree :
def __init__(self) :
self.root = None
def printPreorder(self) :
if (self.root == None) :
return
record = []
# Add first node
record.append(self.root)
node = None
while ((len(record) == 0) == False) :
# Get top element
node = record[-1]
# Remove top element
record.pop()
i = len(node.child) - 1
while (i >= 0) :
record.append(node.child[i])
i -= 1
# Print node value
print(" ", node.key, end = "")
def main() :
tree = NAryTree()
# 10
# / \
# / \
# / \
# 8 5
# /|\ /|\ \
# / | \ / | \ \
# -2 1 6 7 18 3 4
# / \ /| \
# 9 11 2 1 3
# / \
# 17 12
# -----------------------
# 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)
tree.printPreorder()
if __name__ == "__main__": main()Output
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 1 3# Ruby program for
# Iterative Preorder 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 NAryTree
# Define the accessor and reader of class NAryTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
def printPreorder()
if (self.root == nil)
return
end
record = []
# Add first node
record.push(self.root)
node = nil
while (record.length != 0)
# Get top element
node = record.last
# Remove top element
record.pop()
i = node.child.length - 1
while (i >= 0)
record.push(node.child[i])
i -= 1
end
# Print node value
print(" ", node.key)
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
# -----------------------
# 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)
tree.printPreorder()
end
main()Output
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 1 3import scala.collection.mutable._;
// Scala program for
// Iterative Preorder 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 NAryTree(var root: TreeNode)
{
def this()
{
this(null);
}
def printPreorder(): Unit = {
if (this.root == null)
{
return;
}
var record: Stack[TreeNode] = new Stack[TreeNode]();
// Add first node
record.push(this.root);
var node: TreeNode = null;
while (record.isEmpty == false)
{
// Get top element
node = record.top;
// Remove top element
record.pop;
var i: Int = node.child.size - 1;
while (i >= 0)
{
record.push(node.child(i));
i -= 1;
}
// Print node value
print(" " + node.key);
}
}
}
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
-----------------------
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);
tree.printPreorder();
}
}Output
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 1 3import Foundation;
// Swift 4 program for
// Iterative Preorder 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);
}
}
// Stack Node
class SNode
{
var data : TreeNode?;
var next : SNode?;
init(_ data : TreeNode?)
{
self.data = data;
self.next = nil;
}
}
// Define custom stack and its operation
class MyStack
{
var top: SNode? ;
init()
{
self.top = nil;
}
//Add a new element in stack
func push(_ data: TreeNode?)
{
//Make a new stack node
let node: SNode? = SNode(data);
if (node != nil)
{
node!.next = self.top;
self.top = node;
}
else
{
print("Memory overflow\n", terminator: "");
}
}
// Remove a top element in stack
func pop()
{
if (self.top != nil)
{
self.top = self.top!.next;
}
}
// Check that whether stack is empty or not
func isEmpty() -> Bool
{
if (self.top != nil)
{
return false;
}
else
{
return true;
}
}
// Used to get top element of stack
func peek() -> TreeNode?
{
if (self.top != nil)
{
return self.top!.data;
}
else
{
return nil;
}
}
}
class NAryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
func printPreorder()
{
if (self.root == nil)
{
return;
}
let record = MyStack();
// Add first node
record.push(self.root);
var node: TreeNode? = nil;
while (record.isEmpty() == false)
{
// Get top element
node = record.peek();
// Remove top element
record.pop();
var i: Int = node!.child.count - 1;
while (i >= 0)
{
record.push(node!.child[i]);
i -= 1;
}
// Print node value
print(" ", node!.key, terminator: "");
}
}
}
func main()
{
let tree: NAryTree = NAryTree();
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 2 1 3
/ \
17 12
-----------------------
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);
tree.printPreorder();
}
main();Output
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 1 3import java.util.Stack;
// Kotlin program for
// Iterative Preorder 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 NAryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
fun printPreorder(): Unit
{
if (this.root == null)
{
return;
}
val record: Stack < TreeNode > = Stack < TreeNode > ();
// Add first node
record.push(this.root);
var node: TreeNode ? ;
while (record.empty() == false)
{
// Get top element
node = record.peek();
// Remove top element
record.pop();
var i: Int = node!!.child.size - 1;
while (i >= 0)
{
record.push(node.child[i]);
i -= 1;
}
// Print node value
print(" " + node.key);
}
}
}
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
-----------------------
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);
tree.printPreorder();
}Output
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 1 3Time Complexity Analysis
The time complexity of this algorithm depends on the number of nodes in the tree. In the worst case scenario, where each node is visited once, the time complexity is O(n), where n is the number of nodes in the tree.
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