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

## Algorithm Explanation

1. If the root of the tree is null, return.
2. Create an empty stack.
3. Push the root node onto the stack.
4. 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 > ();
}
{
// Create a new node
TreeNode node = new TreeNode(key);
}
}
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 > ();
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);
// Add child node [-2,1,6] in node (8)
// Add child node [9,11] in node (1)
// Add child node [17  12] in node (11)
// Add child node [7 18 3  4] in node (5)
// Add child node [2,1,3] in node (4)
tree.printPreorder();
}
}``````

#### Output

``  10  8  -2  1  9  11  17  12  6  5  7  18  3  4  2  1  3``
``````package 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
}
// Create a new node
var node * TreeNode = getTreeNode(key)
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)
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)
// Add child node [-2,1,6] in node (8)
// Add child node [9,11] in node (1)
// Add child node [17  12] in node (11)
// Add child node [7 18 3  4] in node (5)
// Add child node [2,1,3] in node (4)
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;
}
{
// Create a new node
TreeNode *node = new TreeNode(key);
this->child.push_back(node);
}
};
class NAryTree
{
public: TreeNode *root;
NAryTree()
{
this->root = NULL;
}
void printPreorder()
{
if (this->root == NULL)
{
return;
}
stack < TreeNode *> record;
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);
// Add child node [-2,1,6] in node (8)
// Add child node [9,11] in node (1)
// Add child node [17  12] in node (11)
// Add child node [7 18 3  4] in node (5)
// Add child node [2,1,3] in node (4)
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 > ();
}
{
// Create a new node
TreeNode node = new TreeNode(key);
}
}
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 > ();
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);
// Add child node [-2,1,6] in node (8)
// Add child node [9,11] in node (1)
// Add child node [17  12] in node (11)
// Add child node [7 18 3  4] in node (5)
// Add child node [2,1,3] in node (4)
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();
}
{
// Create a new node
\$node = new TreeNode(\$key);
\$this->child[] = \$node;
}
}
class NAryTree
{
public \$root;
public  function __construct()
{
\$this->root = NULL;
}
public  function printPreorder()
{
if (\$this->root == NULL)
{
return;
}
\$record = array();
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);
// Add child node [-2,1,6] in node (8)
// Add child node [9,11] in node (1)
// Add child node [17  12] in node (11)
// Add child node [7 18 3  4] in node (5)
// Add child node [2,1,3] in node (4)
\$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 = [];
}
{
// Create a new node
var node = new TreeNode(key);
this.child.push(node);
}
}
class NAryTree
{
constructor()
{
this.root = null;
}
printPreorder()
{
if (this.root == null)
{
return;
}
var record = [];
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);
// Add child node [-2,1,6] in node (8)
// Add child node [9,11] in node (1)
// Add child node [17  12] in node (11)
// Add child node [7 18 3  4] in node (5)
// Add child node [2,1,3] in node (4)
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 = []

#  Create a new node
node = TreeNode(key)
self.child.append(node)

class NAryTree :
def __init__(self) :
self.root = None

def printPreorder(self) :
if (self.root == None) :
return

record = []
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)
#  Add child node [-2,1,6] in node (8)
#  Add child node [9,11] in node (1)
#  Add child node [17  12] in node (11)
#  Add child node [7 18 3  4] in node (5)
#  Add child node [2,1,3] in node (4)
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_accessor :key, :child
def initialize(key)
#  Set node key
self.key = key
#  Create memory of TreeNode child
self.child = []
end

#  Create a new node
node = TreeNode.new(key)
self.child.push(node)
end

end

class NAryTree
# Define the accessor and reader of class NAryTree
attr_accessor :root
def initialize()
self.root = nil
end

def printPreorder()
if (self.root == nil)
return
end

record = []
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)
#  Add child node [-2,1,6] in node (8)
#  Add child node [9,11] in node (1)
#  Add child node [17  12] in node (11)
#  Add child node [7 18 3  4] in node (5)
#  Add child node [2,1,3] in node (4)
tree.printPreorder()
end

main()``````

#### Output

``  10  8  -2  1  9  11  17  12  6  5  7  18  3  4  2  1  3``
``````import 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);
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]();
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);
// Add child node [-2,1,6] in node (8)
// Add child node [9,11] in node (1)
// Add child node [17  12] in node (11)
// Add child node [7 18 3  4] in node (5)
// Add child node [2,1,3] in node (4)
tree.printPreorder();
}
}``````

#### Output

``  10  8  -2  1  9  11  17  12  6  5  7  18  3  4  2  1  3``
``````import 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?]();
}
{
// Create a new node
let node: TreeNode = TreeNode(key);
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();
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);
// Add child node [-2,1,6] in node (8)
// Add child node [9,11] in node (1)
// Add child node [17  12] in node (11)
// Add child node [7 18 3  4] in node (5)
// Add child node [2,1,3] in node (4)
tree.printPreorder();
}
main();``````

#### Output

``  10  8  -2  1  9  11  17  12  6  5  7  18  3  4  2  1  3``
``````import 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 > ();
}
{
// Create a new node
val node: TreeNode = TreeNode(key);
}
}
class NAryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
fun printPreorder(): Unit
{
if (this.root == null)
{
return;
}
val record: Stack < TreeNode > = Stack < TreeNode > ();
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);
// Add child node [-2,1,6] in node (8)
// Add child node [9,11] in node (1)
// Add child node [17  12] in node (11)
// Add child node [7 18 3  4] in node (5)
// Add child node [2,1,3] in node (4)
tree.printPreorder();
}``````

#### Output

``  10  8  -2  1  9  11  17  12  6  5  7  18  3  4  2  1  3``

## Time 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.

## Comment

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.