Iterative n-ary tree preorder traversal

Preorder traversal in n-ary tree

Here given code implementation process.

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  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
}
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  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);
        // 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  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?]();
    }
    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  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 > ();
    }
    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  3


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







© 2021, kalkicode.com, All rights reserved