Preorder Tree Traversal of a Binary Tree

That is another form of preorder tree traversal of a binary tree. We can solve this problem in a two way using recursion and iterative.

preorder tree traversal

Recursive approach

This recursive approach start with root node of tree. And follow this steps.

1) When current node are not NULL then print that element value. After that visit left child of this current node. when visited node is not NULL then repeat this step. Otherwise do step 2.

2) Visit the right subtree of current node, if this is not NULL then execute step 1.

Here given code implementation process.

/* 
  Java Program 
  Preorder Tree Traversal of a Binary Tree
  using recursion
*/
// Binary Tree node
class TreeNode
{
    public int data;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data)
    {
        // Set node value
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
class BinaryTree
{
    public TreeNode root;
    public BinaryTree()
    {
        // Set initial tree root
        this.root = null;
    }
    // Display preorder view of binary tree
    public void preorder(TreeNode node)
    {
        if (node != null)
        {
            // Print node value
            System.out.print("  " + node.data);
            // Visit left subtree
            preorder(node.left);
            // Visit right subtree
            preorder(node.right);
        }
    }
    public static void main(String[] args)
    {
        // Create new tree
        BinaryTree tree = new BinaryTree();
        /*  
            Binary Tree
            -------------
                  17
                /    \
              11      21
             / \     /  \
            1   39  10   2
               /
              40
        */
        // Add Tree Node
        tree.root = new TreeNode(17);
        tree.root.left = new TreeNode(11);
        tree.root.right = new TreeNode(21);
        tree.root.right.right = new TreeNode(2);
        tree.root.right.left = new TreeNode(10);
        tree.root.left.left = new TreeNode(1);
        tree.root.left.right = new TreeNode(39);
        tree.root.left.right.left = new TreeNode(40);
        // Display Tree Node
        tree.preorder(tree.root);
    }
}

Output

  17  11  1  39  40  21  10  2
/*
  C Program for
  Preorder Tree Traversal of a Binary Tree
  using Recusion
*/
#include <stdio.h>
#include <stdlib.h>

// Binary Tree node
struct TreeNode
{
    int data;
    struct TreeNode *left, *right;
};
// Binary Tree
struct BinaryTree
{
    struct TreeNode *root;
};
// Create new tree
struct BinaryTree *newTree()
{
    // Create dynamic node
    struct BinaryTree *tree = 
      (struct BinaryTree *) malloc(sizeof(struct BinaryTree));
    if (tree != NULL)
    {
        tree->root = NULL;
    }
    else
    {
        printf("Memory Overflow to Create tree Tree\n");
    }
    // Return new tree
    return tree;
}
// This is creating a binary tree node and return this
struct TreeNode *getNode(int data)
{
    // Create dynamic node
    struct TreeNode *node = 
      (struct TreeNode *) malloc(sizeof(struct TreeNode));
    if (node != NULL)
    {
        // Set data and pointer values
        node->data = data;
        node->left = NULL;
        node->right = NULL;
    }
    else
    {
        // This is indicates, segmentation fault or 
        // Memory overflow problem
        printf("Memory Overflow\n");
    }
    // Return new node
    return node;
}
// Recursive function
// Display preorder view of binary tree
void preorder(struct TreeNode *node)
{
    if (node != NULL)
    {
        // Print node value
        printf("  %d", node->data);
        preorder(node->left);
        preorder(node->right);
    }
}
int main()
{
    struct BinaryTree *tree = newTree();
    /* 
        Binary Tree
        -------------
              17
            /    \
          11      21
         / \     /  \
        1   39  10   2
           /
          40
    */
    // Add Tree Node
    tree->root = getNode(17);
    tree->root->left = getNode(11);
    tree->root->right = getNode(21);
    tree->root->right->right = getNode(2);
    tree->root->right->left = getNode(10);
    tree->root->left->left = getNode(1);
    tree->root->left->right = getNode(39);
    tree->root->left->right->left = getNode(40);
    // Display tree node
    preorder(tree->root);
    return 0;
}

Output

  17  11  1  39  40  21  10  2
// Include header file
#include <iostream>
using namespace std;
/*
  C++ Program 
  Preorder Tree Traversal of a Binary Tree
  using recursion
*/
// Binary Tree node
class TreeNode
{
    public: int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        // Set node value
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
class BinaryTree
{
    public: TreeNode *root;
    BinaryTree()
    {
        this->root = NULL;
    }
    // Display preorder view of binary tree
    void preorder(TreeNode *node)
    {
        if (node != NULL)
        {
            // Print node value
            cout << "  " << node->data;
            // Visit left subtree
            this->preorder(node->left);
            // Visit right subtree
            this->preorder(node->right);
        }
    }
};
int main()
{
    // Create new tree
    BinaryTree *tree = new BinaryTree();
    /*
        Binary Tree
        -------------
              17
            /    \
          11      21
         / \     /  \
        1   39  10   2
           /
          40
    */
    // Add Tree Node
    tree->root = new TreeNode(17);
    tree->root->left = new TreeNode(11);
    tree->root->right = new TreeNode(21);
    tree->root->right->right = new TreeNode(2);
    tree->root->right->left = new TreeNode(10);
    tree->root->left->left = new TreeNode(1);
    tree->root->left->right = new TreeNode(39);
    tree->root->left->right->left = new TreeNode(40);
    // Display Tree Node
    tree->preorder(tree->root);
    return 0;
}

Output

  17  11  1  39  40  21  10  2
package main
import "fmt"
/* 
  Go Program 
  Preorder Tree Traversal of a Binary Tree
  using recursion
*/
// Binary Tree node
type TreeNode struct {
    data int
    left * TreeNode
    right * TreeNode
}
func getTreeNode(data int) * TreeNode {
    var me *TreeNode = &TreeNode {}
    // Set node value
    me.data = data
    me.left = nil
    me.right = nil
    return me
}
type BinaryTree struct {
    root * TreeNode
}
func getBinaryTree() * BinaryTree {
    var me *BinaryTree = &BinaryTree {}
    // Set initial tree root
    me.root = nil
    return me
}
// Display preorder view of binary tree
func(this BinaryTree) preorder(node * TreeNode) {
    if node != nil {
        // Print node value
        fmt.Print("  ", node.data)
        // Visit left subtree
        this.preorder(node.left)
        // Visit right subtree
        this.preorder(node.right)
    }
}
func main() {
    // Create new tree
    var tree * BinaryTree = getBinaryTree()
    /*
        Binary Tree
        -------------
              17
            /    \
          11      21
         / \     /  \
        1   39  10   2
           /
          40
    */
    // Add Tree Node
    tree.root = getTreeNode(17)
    tree.root.left = getTreeNode(11)
    tree.root.right = getTreeNode(21)
    tree.root.right.right = getTreeNode(2)
    tree.root.right.left = getTreeNode(10)
    tree.root.left.left = getTreeNode(1)
    tree.root.left.right = getTreeNode(39)
    tree.root.left.right.left = getTreeNode(40)
    // Display Tree Node
    tree.preorder(tree.root)
}

Output

  17  11  1  39  40  21  10  2
// Include namespace system
using System;
/* 
  Csharp Program 
  Preorder Tree Traversal of a Binary Tree
  using recursion
*/
// Binary Tree node
public class TreeNode
{
    public int data;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data)
    {
        // Set node value
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
public class BinaryTree
{
    public TreeNode root;
    public BinaryTree()
    {
        // Set initial tree root
        this.root = null;
    }
    // Display preorder view of binary tree
    public void preorder(TreeNode node)
    {
        if (node != null)
        {
            // Print node value
            Console.Write("  " + node.data);
            // Visit left subtree
            this.preorder(node.left);
            // Visit right subtree
            this.preorder(node.right);
        }
    }
    public static void Main(String[] args)
    {
        // Create new tree
        BinaryTree tree = new BinaryTree();
        /*
            Binary Tree
            -------------
                  17
                /    \
              11      21
             / \     /  \
            1   39  10   2
               /
              40
        */
        // Add Tree Node
        tree.root = new TreeNode(17);
        tree.root.left = new TreeNode(11);
        tree.root.right = new TreeNode(21);
        tree.root.right.right = new TreeNode(2);
        tree.root.right.left = new TreeNode(10);
        tree.root.left.left = new TreeNode(1);
        tree.root.left.right = new TreeNode(39);
        tree.root.left.right.left = new TreeNode(40);
        // Display Tree Node
        tree.preorder(tree.root);
    }
}

Output

  17  11  1  39  40  21  10  2
<?php
/* 
  Php Program 
  Preorder Tree Traversal of a Binary Tree
  using recursion
*/
// Binary Tree node
class TreeNode
{
    public $data;
    public $left;
    public $right;
    public  function __construct($data)
    {
        // Set node value
        $this->data = $data;
        $this->left = NULL;
        $this->right = NULL;
    }
}
class BinaryTree
{
    public $root;
    public  function __construct()
    {
        $this->root = NULL;
    }
    // Display preorder view of binary tree
    public  function preorder($node)
    {
        if ($node != NULL)
        {
            // Print node value
            echo("  ".$node->data);
            // Visit left subtree
            $this->preorder($node->left);
            // Visit right subtree
            $this->preorder($node->right);
        }
    }
}

function main()
{
    // Create new tree
    $tree = new BinaryTree();
    /*
        Binary Tree
        -------------
              17
            /    \
          11      21
         / \     /  \
        1   39  10   2
           /
          40
    */
    // Add Tree Node
    $tree->root = new TreeNode(17);
    $tree->root->left = new TreeNode(11);
    $tree->root->right = new TreeNode(21);
    $tree->root->right->right = new TreeNode(2);
    $tree->root->right->left = new TreeNode(10);
    $tree->root->left->left = new TreeNode(1);
    $tree->root->left->right = new TreeNode(39);
    $tree->root->left->right->left = new TreeNode(40);
    // Display Tree Node
    $tree->preorder($tree->root);
}
main();

Output

  17  11  1  39  40  21  10  2
/* 
  Node JS Program 
  Preorder Tree Traversal of a Binary Tree
  using recursion
*/
// Binary Tree node
class TreeNode
{
    constructor(data)
    {
        // Set node value
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
class BinaryTree
{
    constructor()
    {
        this.root = null;
    }
    // Display preorder view of binary tree
    preorder(node)
    {
        if (node != null)
        {
            // Print node value
            process.stdout.write("  " + node.data);
            // Visit left subtree
            this.preorder(node.left);
            // Visit right subtree
            this.preorder(node.right);
        }
    }
}

function main()
{
    // Create new tree
    var tree = new BinaryTree();
    /*
        Binary Tree
        -------------
              17
            /    \
          11      21
         / \     /  \
        1   39  10   2
           /
          40
    */
    // Add Tree Node
    tree.root = new TreeNode(17);
    tree.root.left = new TreeNode(11);
    tree.root.right = new TreeNode(21);
    tree.root.right.right = new TreeNode(2);
    tree.root.right.left = new TreeNode(10);
    tree.root.left.left = new TreeNode(1);
    tree.root.left.right = new TreeNode(39);
    tree.root.left.right.left = new TreeNode(40);
    // Display Tree Node
    tree.preorder(tree.root);
}
main();

Output

  17  11  1  39  40  21  10  2
#  Python 3 Program 
#  Preorder Tree Traversal of a Binary Tree
#  using recursion

#  Binary Tree node
class TreeNode :
    def __init__(self, data) :
        #  Set node value
        self.data = data
        self.left = None
        self.right = None
    

class BinaryTree :
    def __init__(self) :
        self.root = None
    
    #  Display preorder view of binary tree
    def preorder(self, node) :
        if (node != None) :
            #  Print node value
            print("  ", node.data, end = "")
            #  Visit left subtree
            self.preorder(node.left)
            #  Visit right subtree
            self.preorder(node.right)
        
    

def main() :
    #  Create new tree
    tree = BinaryTree()
    #    Binary Tree
    #    -------------
    #          17
    #        /    \
    #      11      21
    #     / \     /  \
    #    1   39  10   2
    #       /
    #      40
    #  Add Tree Node
    tree.root = TreeNode(17)
    tree.root.left = TreeNode(11)
    tree.root.right = TreeNode(21)
    tree.root.right.right = TreeNode(2)
    tree.root.right.left = TreeNode(10)
    tree.root.left.left = TreeNode(1)
    tree.root.left.right = TreeNode(39)
    tree.root.left.right.left = TreeNode(40)
    #  Display Tree Node
    tree.preorder(tree.root)

if __name__ == "__main__": main()

Output

   17   11   1   39   40   21   10   2
#  Ruby Program 
#  Preorder Tree Traversal of a Binary Tree
#  using recursion

#  Binary Tree node
class TreeNode 
    # Define the accessor and reader of class TreeNode
    attr_reader :data, :left, :right
    attr_accessor :data, :left, :right
    def initialize(data) 
        #  Set node value
        self.data = data
        self.left = nil
        self.right = nil
    end

end

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

    #  Display preorder view of binary tree
    def preorder(node) 
        if (node != nil) 
            #  Print node value
            print("  ", node.data)
            #  Visit left subtree
            self.preorder(node.left)
            #  Visit right subtree
            self.preorder(node.right)
        end

    end

end

def main() 
    #  Create new tree
    tree = BinaryTree.new()
    #    Binary Tree
    #    -------------
    #          17
    #        /    \
    #      11      21
    #     / \     /  \
    #    1   39  10   2
    #       /
    #      40
    #  Add Tree Node
    tree.root = TreeNode.new(17)
    tree.root.left = TreeNode.new(11)
    tree.root.right = TreeNode.new(21)
    tree.root.right.right = TreeNode.new(2)
    tree.root.right.left = TreeNode.new(10)
    tree.root.left.left = TreeNode.new(1)
    tree.root.left.right = TreeNode.new(39)
    tree.root.left.right.left = TreeNode.new(40)
    #  Display Tree Node
    tree.preorder(tree.root)
end

main()

Output

  17  11  1  39  40  21  10  2
/* 
  Scala Program 
  Preorder Tree Traversal of a Binary Tree
  using recursion
*/
// Binary Tree node
class TreeNode(var data: Int,
    var left: TreeNode,
        var right: TreeNode)
{
    def this(data: Int)
    {
        // Set node value
        this(data, null, null);
    }
}
class BinaryTree(var root: TreeNode)
{
    def this()
    {
        
        this(null);
    }
    // Display preorder view of binary tree
    def preorder(node: TreeNode): Unit = {
        if (node != null)
        {
            // Print node value
            print("  " + node.data);
            // Visit left subtree
            preorder(node.left);
            // Visit right subtree
            preorder(node.right);
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        // Create new tree
        var tree: BinaryTree = new BinaryTree();
        /*
            Binary Tree
            -------------
                  17
                /    \
              11      21
             / \     /  \
            1   39  10   2
               /
              40
        */
        // Add Tree Node
        tree.root = new TreeNode(17);
        tree.root.left = new TreeNode(11);
        tree.root.right = new TreeNode(21);
        tree.root.right.right = new TreeNode(2);
        tree.root.right.left = new TreeNode(10);
        tree.root.left.left = new TreeNode(1);
        tree.root.left.right = new TreeNode(39);
        tree.root.left.right.left = new TreeNode(40);
        // Display Tree Node
        tree.preorder(tree.root);
    }
}

Output

  17  11  1  39  40  21  10  2
/* 
  Swift 4 Program 
  Preorder Tree Traversal of a Binary Tree
  using recursion
*/
// Binary Tree node
class TreeNode
{
    var data: Int;
    var left: TreeNode? ;
    var right: TreeNode? ;
    init(_ data: Int)
    {
        // Set node value
        self.data = data;
        self.left = nil;
        self.right = nil;
    }
}
class BinaryTree
{
    var root: TreeNode? ;
    init()
    {
        self.root = nil;
    }
    // Display preorder view of binary tree
    func preorder(_ node: TreeNode? )
    {
        if (node  != nil)
        {
            // Print node value
            print("  ", node!.data, terminator: "");
            // Visit left subtree
            self.preorder(node!.left);
            // Visit right subtree
            self.preorder(node!.right);
        }
    }
}
func main()
{
    // Create new tree
    let tree: BinaryTree = BinaryTree();
    /*
        Binary Tree
        -------------
              17
            /    \
          11      21
         / \     /  \
        1   39  10   2
           /
          40
    */
    // Add Tree Node
    tree.root = TreeNode(17);
    tree.root!.left = TreeNode(11);
    tree.root!.right = TreeNode(21);
    tree.root!.right!.right = TreeNode(2);
    tree.root!.right!.left = TreeNode(10);
    tree.root!.left!.left = TreeNode(1);
    tree.root!.left!.right = TreeNode(39);
    tree.root!.left!.right!.left = TreeNode(40);
    // Display Tree Node
    tree.preorder(tree.root);
}
main();

Output

   17   11   1   39   40   21   10   2
/* 
  Kotlin Program 
  Preorder Tree Traversal of a Binary Tree
  using recursion
*/
// Binary Tree node
class TreeNode
{
    var data: Int;
    var left: TreeNode ? ;
    var right: TreeNode ? ;
    constructor(data: Int)
    {
        // Set node value
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
class BinaryTree
{
    var root: TreeNode ? ;
    constructor()
    {
        this.root = null;
    }
    // Display preorder view of binary tree
    fun preorder(node: TreeNode ? ): Unit
    {
        if (node != null)
        {
            // Print node value
            print("  " + node.data);
            // Visit left subtree
            this.preorder(node.left);
            // Visit right subtree
            this.preorder(node.right);
        }
    }
}
fun main(args: Array < String > ): Unit
{
    // Create new tree
    val tree: BinaryTree = BinaryTree();
    /*
        Binary Tree
        -------------
              17
            /    \
          11      21
         / \     /  \
        1   39  10   2
           /
          40
    */
    // Add Tree Node
    tree.root = TreeNode(17);
    tree.root?.left = TreeNode(11);
    tree.root?.right = TreeNode(21);
    tree.root?.right?.right = TreeNode(2);
    tree.root?.right?.left = TreeNode(10);
    tree.root?.left?.left = TreeNode(1);
    tree.root?.left?.right = TreeNode(39);
    tree.root?.left?.right?.left = TreeNode(40);
    // Display Tree Node
    tree.preorder(tree.root);
}

Output

  17  11  1  39  40  21  10  2

Iterative approach

When we are need to traverse tree preorder form. Then we can used stack data structure to solve this problem.

/*
  C Program 
  Preorder Tree Traversal of a Binary Tree
  Using Stack
*/
#include <stdio.h>
#include <stdlib.h>

// Binary Tree node
struct TreeNode
{
    int data;
    struct TreeNode *left, *right;
};
// Binary Tree
struct BinaryTree
{
    struct TreeNode *root;
};
// Stack Node
struct StackNode
{
    struct TreeNode *element;
    struct StackNode *next;
};
// Define a custom stack
struct MyStack
{
    struct StackNode *top;
    int size;
};
struct MyStack *newStack()
{
    // Make a stack
    struct MyStack *stack = (struct MyStack *) malloc(sizeof(struct MyStack));
    if (stack != NULL)
    {
        // Set node values
        stack->top = NULL;
        stack->size = 0;
    }
    else
    {
        printf("\nMemory overflow when create new stack\n");
    }
    return stack;
}
// Returns the status of empty or non empty stacks
int isEmpty(struct MyStack *stack)
{
    if (stack->size > 0 && stack->top != NULL)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}
// Add node at the top of stack
void push(struct MyStack *stack, struct TreeNode *element)
{
    // Make a new node
    struct StackNode *node = 
      (struct StackNode *) malloc(sizeof(struct StackNode));
    if (node == NULL)
    {
        printf("\nMemory overflow when create new stack Node \n");
    }
    else
    {
        node->element = element;
        node->next = stack->top;
    }
    // Add stack element
    stack->top = node;
    stack->size++;
}
// Return top element of stack
struct TreeNode *peek(struct MyStack *stack)
{
    if (stack == NULL)
    {
        return NULL;
    }
    return stack->top->element;
}
// Remove top element of stack
void pop(struct MyStack *stack)
{
    if (!isEmpty(stack))
    {
        struct StackNode *temp = stack->top;
        // Change top element of stack
        stack->top = temp->next;
        // remove previous top
        free(temp);
        temp = NULL;
        stack->size--;
    }
}
// Create new tree
struct BinaryTree *newTree()
{
    // Create dynamic node
    struct BinaryTree *tree = 
      (struct BinaryTree *) malloc(sizeof(struct BinaryTree));
    if (tree != NULL)
    {
        tree->root = NULL;
    }
    else
    {
        printf("Memory Overflow to Create tree Tree\n");
    }
    // Return new tree
    return tree;
}
// This is creating a binary tree node and return this
struct TreeNode *getNode(int data)
{
    // Create dynamic node
    struct TreeNode *node = 
      (struct TreeNode *) malloc(sizeof(struct TreeNode));
    if (node != NULL)
    {
        // Set data and pointer values
        node->data = data;
        node->left = NULL;
        node->right = NULL;
    }
    else
    {
        // This is indicates, segmentation fault or 
        // Memory overflow problem
        printf("Memory Overflow\n");
    }
    // Return new node
    return node;
}
// Display preorder view of binary tree
void preorder(struct TreeNode *root)
{
    if (root != NULL)
    {
        // Make new stack 
        struct MyStack *s = newStack();
        struct TreeNode *node = root;
        // Display tree element
        while (!isEmpty(s) || node != NULL)
        {
            if (node != NULL)
            {
                // Display node value
                printf("%d  ", node->data);
                // Add current node
                push(s, node);
                // Visit to left subtree
                node = node->left;
            }
            else
            {
                // When node is null
                // Get stack top element
                node = peek(s);
              
                // Remove top element of the stack
                pop(s);
                // Visit to left subtree of current node
                node = node->right;
            }
        }
    }
    else
    {
        printf("Empty Linked List\n");
    }
}
int main()
{
    struct BinaryTree *tree = newTree();
    /* 
        Binary Tree
        -------------
              17
            /    \
          11      21
         / \     /  \
        1   39  10   2
           /
          40
    */
    // Add Tree Node
    tree->root = getNode(17);
    tree->root->left = getNode(11);
    tree->root->right = getNode(21);
    tree->root->right->right = getNode(2);
    tree->root->right->left = getNode(10);
    tree->root->left->left = getNode(1);
    tree->root->left->right = getNode(39);
    tree->root->left->right->left = getNode(40);
    // Display Tree elements
    preorder(tree->root);
    return 0;
}

Output

17  11  1  39  40  21  10  2
// Java Program 
// Preorder traversal without recursion
// Using stack

// Binary Tree node
class TreeNode
{
    public int data;
    public TreeNode left;
    public TreeNode right;
    // Make a tree node
    public TreeNode(int data)
    {
        // Set node data
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
class StackNode
{
    public TreeNode element;
    public StackNode next;
    public StackNode(TreeNode element)
    {
        this.element = element;
        this.next = null;
    }
}
// Stack Class
class MyStack
{
    public StackNode top;
    public int size;
    public MyStack()
    {
        this.top = null;
        this.size = 0;
    }
    // Add new element into stack
    public void push(TreeNode element)
    {
        // Create new node
        StackNode node = new StackNode(element);
        node.next = this.top;
        // new node is new top
        this.top = node;
        // Increase the size
        this.size += 1;
    }
    // Remove top element of the stack
    public void pop()
    {
        if (this.top != null)
        {
            // next node is new top
            this.top = this.top.next;
            // Reduce size
            this.size -= 1;
        }
    }
    // Returns the status of empty or non empty stacks
    public boolean isEmpty()
    {
        if (this.size > 0 && this.top != null)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    // Return top element of stack
    public TreeNode peek()
    {
        if (isEmpty())
        {
            return null;
        }
        return this.top.element;
    }
}
public class BinaryTree
{
    public TreeNode root;
    public BinaryTree()
    {
        // Set initial tree root to null
        this.root = null;
    }
    // Display preorder view of binary tree
    public void preorder()
    {
        if (this.root != null)
        {
            // Make new stack 
            MyStack s = new MyStack();
            TreeNode node = this.root;
            // Display tree element
            while (!s.isEmpty() || node != null)
            {
                if (node != null)
                {
                    // Display node value
                    System.out.print(" " + node.data);
                    // Add current node
                    s.push(node);
                    // Visit to left subtree
                    node = node.left;
                }
                else
                {
                    // When node is null
                    // Get stack top element
                    node = s.peek();
                    // Remove top element of the stack
                    s.pop();
                    // Visit to left subtree of current node
                    node = node.right;
                }
            }
        }
        else
        {
            System.out.print("Empty Linked List\n");
        }
    }
    public static void main(String[] args)
    {
        // Create new tree
        BinaryTree tree = new BinaryTree();
        /* 
            Binary Tree
            -------------
                  17
                /    \
              11      21
             / \     /  \
            1   39  10   2
               /
              40
        */
        // Add Tree Node
        tree.root = new TreeNode(17);
        tree.root.left = new TreeNode(11);
        tree.root.right = new TreeNode(21);
        tree.root.right.right = new TreeNode(2);
        tree.root.right.left = new TreeNode(10);
        tree.root.left.left = new TreeNode(1);
        tree.root.left.right = new TreeNode(39);
        tree.root.left.right.left = new TreeNode(40);
        // Display Tree Node
        tree.preorder();
    }
}

Output

 17 11 1 39 40 21 10 2
// Include header file
#include <iostream>
using namespace std;
// C++ Program
// Preorder traversal without recursion
// Using stack

// Binary Tree node
class TreeNode
{
    public: int data;
    TreeNode *left;
    TreeNode *right;
    // Make a tree node
    TreeNode(int data)
    {
        // Set node data
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
class StackNode
{
    public: TreeNode *element;
    StackNode *next;
    StackNode(TreeNode *element)
    {
        this->element = element;
        this->next = NULL;
    }
};
// Stack Class
class MyStack
{
    public: StackNode *top;
    int size;
    MyStack()
    {
        this->top = NULL;
        this->size = 0;
    }
    // Add new element into stack
    void push(TreeNode *element)
    {
        // Create new node
        StackNode *node = new StackNode(element);
        node->next = this->top;
        // new node is new top
        this->top = node;
        // Increase the size
        this->size += 1;
    }
    // Remove top element of the stack
    void pop()
    {
        if (this->top != NULL)
        {
            struct StackNode *temp = this->top;
            // next node is new top
            this->top = this->top->next;
            // Reduce size
            this->size -= 1;
            // Free memory
            delete temp;
        }
    }
    // Returns the status of empty or non empty stacks
    bool isEmpty()
    {
        if (this->size > 0 && this->top != NULL)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    // Return top element of stack
    TreeNode *peek()
    {
        if (this->isEmpty())
        {
            return NULL;
        }
        return this->top->element;
    }
};
class BinaryTree
{
    public: TreeNode *root;
    BinaryTree()
    {
        this->root = NULL;
    }
    // Display preorder view of binary tree
    void preorder()
    {
        if (this->root != NULL)
        {
            // Make new stack
            MyStack *s = new MyStack();
            TreeNode *node = this->root;
            // Display tree element
            while (!s->isEmpty() || node != NULL)
            {
                if (node != NULL)
                {
                    // Display node value
                    cout << " " << node->data;
                    // Add current node
                    s->push(node);
                    // Visit to left subtree
                    node = node->left;
                }
                else
                {
                    // When node is null
                    // Get stack top element
                    node = s->peek();
                    // Remove top element of the stack
                    s->pop();
                    // Visit to left subtree of current node
                    node = node->right;
                }
            }
        }
        else
        {
            cout << "Empty Linked List\n";
        }
    }
};
int main()
{
    // Create new tree
    BinaryTree *tree = new BinaryTree();
    /*
        Binary Tree
        -------------
              17
            /    \
          11      21
         / \     /  \
        1   39  10   2
           /
          40
    */
    // Add Tree Node
    tree->root = new TreeNode(17);
    tree->root->left = new TreeNode(11);
    tree->root->right = new TreeNode(21);
    tree->root->right->right = new TreeNode(2);
    tree->root->right->left = new TreeNode(10);
    tree->root->left->left = new TreeNode(1);
    tree->root->left->right = new TreeNode(39);
    tree->root->left->right->left = new TreeNode(40);
    // Display Tree Node
    tree->preorder();
    return 0;
}

Output

 17 11 1 39 40 21 10 2
package main
import "fmt"
// Go Program
// Preorder traversal without recursion
// Using stack
// Binary Tree node
type TreeNode struct {
    data int
    left * TreeNode
    right * TreeNode
}
func getTreeNode(data int) * TreeNode {
    var me *TreeNode = &TreeNode {}
    // Set node data
    me.data = data
    me.left = nil
    me.right = nil
    return me
}
type StackNode struct {
    element * TreeNode
    next * StackNode
}
func getStackNode(element * TreeNode) * StackNode {
    var me *StackNode = &StackNode {}
    me.element = element
    me.next = nil
    return me
}
// Stack Class
type MyStack struct {
    top * StackNode
    size int
}
func getMyStack() * MyStack {
    var me *MyStack = &MyStack {}
    me.top = nil
    me.size = 0
    return me
}
// Add new element into stack
func(this *MyStack) push(element * TreeNode) {
    // Create new node
    var node * StackNode = getStackNode(element)
    node.next = this.top
    // new node is new top
    this.top = node
    // Increase the size
    this.size += 1
}
// Remove top element of the stack
func(this *MyStack) pop() {
    if this.top != nil {
        // next node is new top
        this.top = this.top.next
        // Reduce size
        this.size -= 1
    }
}
// Returns the status of empty or non empty stacks
func(this MyStack) isEmpty() bool {
    if this.size > 0 && this.top != nil {
        return false
    } else {
        return true
    }
}
// Return top element of stack
func(this MyStack) peek() * TreeNode {
    if this.isEmpty() {
        return nil
    }
    return this.top.element
}
type BinaryTree struct {
    root * TreeNode
}
func getBinaryTree() * BinaryTree {
    var me *BinaryTree = &BinaryTree {}
    // Set initial tree root to null
    me.root = nil
    return me
}
// Display preorder view of binary tree
func(this BinaryTree) preorder() {
    if this.root != nil {
        // Make new stack
        var s * MyStack = getMyStack()
        var node * TreeNode = this.root
        // Display tree element
        for (!s.isEmpty() || node != nil) {
            if node != nil {
                // Display node value
                fmt.Print(" ", node.data)
                // Add current node
                s.push(node)
                // Visit to left subtree
                node = node.left
            } else {
                // When node is null
                // Get stack top element
                node = s.peek()
                // Remove top element of the stack
                s.pop()
                // Visit to left subtree of current node
                node = node.right
            }
        }
    } else {
        fmt.Print("Empty Linked List\n")
    }
}
func main() {
    // Create new tree
    var tree * BinaryTree = getBinaryTree()
    /*
        Binary Tree
        -------------
              17
            /    \
          11      21
         / \     /  \
        1   39  10   2
           /
          40
    */
    // Add Tree Node
    tree.root = getTreeNode(17)
    tree.root.left = getTreeNode(11)
    tree.root.right = getTreeNode(21)
    tree.root.right.right = getTreeNode(2)
    tree.root.right.left = getTreeNode(10)
    tree.root.left.left = getTreeNode(1)
    tree.root.left.right = getTreeNode(39)
    tree.root.left.right.left = getTreeNode(40)
    // Display Tree Node
    tree.preorder()
}

Output

 17 11 1 39 40 21 10 2
// Include namespace system
using System;
// Csharp Program
// Preorder traversal without recursion
// Using stack

// Binary Tree node
public class TreeNode
{
    public int data;
    public TreeNode left;
    public TreeNode right;
    // Make a tree node
    public TreeNode(int data)
    {
        // Set node data
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
public class StackNode
{
    public TreeNode element;
    public StackNode next;
    public StackNode(TreeNode element)
    {
        this.element = element;
        this.next = null;
    }
}
// Stack Class
public class MyStack
{
    public StackNode top;
    public int size;
    public MyStack()
    {
        this.top = null;
        this.size = 0;
    }
    // Add new element into stack
    public void push(TreeNode element)
    {
        // Create new node
        StackNode node = new StackNode(element);
        node.next = this.top;
        // new node is new top
        this.top = node;
        // Increase the size
        this.size += 1;
    }
    // Remove top element of the stack
    public void pop()
    {
        if (this.top != null)
        {
            // next node is new top
            this.top = this.top.next;
            // Reduce size
            this.size -= 1;
        }
    }
    // Returns the status of empty or non empty stacks
    public Boolean isEmpty()
    {
        if (this.size > 0 && this.top != null)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    // Return top element of stack
    public TreeNode peek()
    {
        if (this.isEmpty())
        {
            return null;
        }
        return this.top.element;
    }
}
public class BinaryTree
{
    public TreeNode root;
    public BinaryTree()
    {
        // Set initial tree root to null
        this.root = null;
    }
    // Display preorder view of binary tree
    public void preorder()
    {
        if (this.root != null)
        {
            // Make new stack
            MyStack s = new MyStack();
            TreeNode node = this.root;
            // Display tree element
            while (!s.isEmpty() || node != null)
            {
                if (node != null)
                {
                    // Display node value
                    Console.Write(" " + node.data);
                    // Add current node
                    s.push(node);
                    // Visit to left subtree
                    node = node.left;
                }
                else
                {
                    // When node is null
                    // Get stack top element
                    node = s.peek();
                    // Remove top element of the stack
                    s.pop();
                    // Visit to left subtree of current node
                    node = node.right;
                }
            }
        }
        else
        {
            Console.Write("Empty Linked List\n");
        }
    }
    public static void Main(String[] args)
    {
        // Create new tree
        BinaryTree tree = new BinaryTree();
        /*
            Binary Tree
            -------------
                  17
                /    \
              11      21
             / \     /  \
            1   39  10   2
               /
              40
        */
        // Add Tree Node
        tree.root = new TreeNode(17);
        tree.root.left = new TreeNode(11);
        tree.root.right = new TreeNode(21);
        tree.root.right.right = new TreeNode(2);
        tree.root.right.left = new TreeNode(10);
        tree.root.left.left = new TreeNode(1);
        tree.root.left.right = new TreeNode(39);
        tree.root.left.right.left = new TreeNode(40);
        // Display Tree Node
        tree.preorder();
    }
}

Output

 17 11 1 39 40 21 10 2
<?php
// Php Program
// Preorder traversal without recursion
// Using stack

// Binary Tree node
class TreeNode
{
    public $data;
    public $left;
    public $right;
    // Make a tree node
    public  function __construct($data)
    {
        // Set node data
        $this->data = $data;
        $this->left = NULL;
        $this->right = NULL;
    }
}
class StackNode
{
    public $element;
    public $next;
    public  function __construct($element)
    {
        $this->element = $element;
        $this->next = NULL;
    }
}
// Stack Class
class MyStack
{
    public $top;
    public $size;
    public  function __construct()
    {
        $this->top = NULL;
        $this->size = 0;
    }
    // Add new element into stack
    public  function push($element)
    {
        // Create new node
        $node = new StackNode($element);
        $node->next = $this->top;
        // new node is new top
        $this->top = $node;
        // Increase the size
        $this->size += 1;
    }
    // Remove top element of the stack
    public  function pop()
    {
        if ($this->top != NULL)
        {
            // next node is new top
            $this->top = $this->top->next;
            // Reduce size
            $this->size -= 1;
        }
    }
    // Returns the status of empty or non empty stacks
    public  function isEmpty()
    {
        if ($this->size > 0 && $this->top != NULL)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    // Return top element of stack
    public  function peek()
    {
        if ($this->isEmpty())
        {
            return NULL;
        }
        return $this->top->element;
    }
}
class BinaryTree
{
    public $root;
    public  function __construct()
    {
        $this->root = NULL;
    }
    // Display preorder view of binary tree
    public  function preorder()
    {
        if ($this->root != NULL)
        {
            // Make new stack
            $s = new MyStack();
            $node = $this->root;
            // Display tree element
            while (!$s->isEmpty() || $node != NULL)
            {
                if ($node != NULL)
                {
                    // Display node value
                    echo(" ".$node->data);
                    // Add current node
                    $s->push($node);
                    // Visit to left subtree
                    $node = $node->left;
                }
                else
                {
                    // When node is null
                    // Get stack top element
                    $node = $s->peek();
                    // Remove top element of the stack
                    $s->pop();
                    // Visit to left subtree of current node
                    $node = $node->right;
                }
            }
        }
        else
        {
            echo("Empty Linked List\n");
        }
    }
}

function main()
{
    // Create new tree
    $tree = new BinaryTree();
    /*
        Binary Tree
        -------------
              17
            /    \
          11      21
         / \     /  \
        1   39  10   2
           /
          40
    */
    // Add Tree Node
    $tree->root = new TreeNode(17);
    $tree->root->left = new TreeNode(11);
    $tree->root->right = new TreeNode(21);
    $tree->root->right->right = new TreeNode(2);
    $tree->root->right->left = new TreeNode(10);
    $tree->root->left->left = new TreeNode(1);
    $tree->root->left->right = new TreeNode(39);
    $tree->root->left->right->left = new TreeNode(40);
    // Display Tree Node
    $tree->preorder();
}
main();

Output

 17 11 1 39 40 21 10 2
// Node JS Program
// Preorder traversal without recursion
// Using stack

// Binary Tree node
class TreeNode
{
    // Make a tree node
    constructor(data)
    {
        // Set node data
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
class StackNode
{
    constructor(element)
    {
        this.element = element;
        this.next = null;
    }
}
// Stack Class
class MyStack
{
    constructor()
    {
        this.top = null;
        this.size = 0;
    }
    // Add new element into stack
    push(element)
    {
        // Create new node
        var node = new StackNode(element);
        node.next = this.top;
        // new node is new top
        this.top = node;
        // Increase the size
        this.size += 1;
    }
    // Remove top element of the stack
    pop()
    {
        if (this.top != null)
        {
            // next node is new top
            this.top = this.top.next;
            // Reduce size
            this.size -= 1;
        }
    }
    // Returns the status of empty or non empty stacks
    isEmpty()
    {
        if (this.size > 0 && this.top != null)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    // Return top element of stack
    peek()
    {
        if (this.isEmpty())
        {
            return null;
        }
        return this.top.element;
    }
}
class BinaryTree
{
    constructor()
    {
        this.root = null;
    }
    // Display preorder view of binary tree
    preorder()
    {
        if (this.root != null)
        {
            // Make new stack
            var s = new MyStack();
            var node = this.root;
            // Display tree element
            while (!s.isEmpty() || node != null)
            {
                if (node != null)
                {
                    // Display node value
                    process.stdout.write(" " + node.data);
                    // Add current node
                    s.push(node);
                    // Visit to left subtree
                    node = node.left;
                }
                else
                {
                    // When node is null
                    // Get stack top element
                    node = s.peek();
                    // Remove top element of the stack
                    s.pop();
                    // Visit to left subtree of current node
                    node = node.right;
                }
            }
        }
        else
        {
            process.stdout.write("Empty Linked List\n");
        }
    }
}

function main()
{
    // Create new tree
    var tree = new BinaryTree();
    /*
        Binary Tree
        -------------
              17
            /    \
          11      21
         / \     /  \
        1   39  10   2
           /
          40
    */
    // Add Tree Node
    tree.root = new TreeNode(17);
    tree.root.left = new TreeNode(11);
    tree.root.right = new TreeNode(21);
    tree.root.right.right = new TreeNode(2);
    tree.root.right.left = new TreeNode(10);
    tree.root.left.left = new TreeNode(1);
    tree.root.left.right = new TreeNode(39);
    tree.root.left.right.left = new TreeNode(40);
    // Display Tree Node
    tree.preorder();
}
main();

Output

 17 11 1 39 40 21 10 2
#  Python 3 Program
#  Preorder traversal without recursion
#  Using stack

#  Binary Tree node
class TreeNode :
    #  Make a tree node
    def __init__(self, data) :
        #  Set node data
        self.data = data
        self.left = None
        self.right = None
    

class StackNode :
    def __init__(self, element) :
        self.element = element
        self.next = None
    

#  Stack Class
class MyStack :
    def __init__(self) :
        self.top = None
        self.size = 0
    
    #  Add new element into stack
    def push(self, element) :
        #  Create new node
        node = StackNode(element)
        node.next = self.top
        #  new node is new top
        self.top = node
        #  Increase the size
        self.size += 1
    
    #  Remove top element of the stack
    def pop(self) :
        if (self.top != None) :
            #  next node is new top
            self.top = self.top.next
            #  Reduce size
            self.size -= 1
        
    
    #  Returns the status of empty or non empty stacks
    def isEmpty(self) :
        if (self.size > 0 and self.top != None) :
            return False
        else :
            return True
        
    
    #  Return top element of stack
    def peek(self) :
        if (self.isEmpty()) :
            return None
        
        return self.top.element
    

class BinaryTree :
    def __init__(self) :
        self.root = None
    
    #  Display preorder view of binary tree
    def preorder(self) :
        if (self.root != None) :
            #  Make new stack
            s = MyStack()
            node = self.root
            #  Display tree element
            while (not s.isEmpty() or node != None) :
                if (node != None) :
                    #  Display node value
                    print(" ", node.data, end = "")
                    #  Add current node
                    s.push(node)
                    #  Visit to left subtree
                    node = node.left
                else :
                    #  When node is null
                    #  Get stack top element
                    node = s.peek()
                    #  Remove top element of the stack
                    s.pop()
                    #  Visit to left subtree of current node
                    node = node.right
                
            
        else :
            print("Empty Linked List")
        
    

def main() :
    #  Create new tree
    tree = BinaryTree()
    #    Binary Tree
    #    -------------
    #          17
    #        /    \
    #      11      21
    #     / \     /  \
    #    1   39  10   2
    #       /
    #      40
    #  Add Tree Node
    tree.root = TreeNode(17)
    tree.root.left = TreeNode(11)
    tree.root.right = TreeNode(21)
    tree.root.right.right = TreeNode(2)
    tree.root.right.left = TreeNode(10)
    tree.root.left.left = TreeNode(1)
    tree.root.left.right = TreeNode(39)
    tree.root.left.right.left = TreeNode(40)
    #  Display Tree Node
    tree.preorder()

if __name__ == "__main__": main()

Output

  17  11  1  39  40  21  10  2
#  Ruby Program
#  Preorder traversal without recursion
#  Using stack

#  Binary Tree node
class TreeNode 
    # Define the accessor and reader of class TreeNode
    attr_reader :data, :left, :right
    attr_accessor :data, :left, :right
    #  Make a tree node
    def initialize(data) 
        #  Set node data
        self.data = data
        self.left = nil
        self.right = nil
    end

end

class StackNode 
    # Define the accessor and reader of class StackNode
    attr_reader :element, :next
    attr_accessor :element, :next
    def initialize(element) 
        self.element = element
        self.next = nil
    end

end

#  Stack Class
class MyStack 
    # Define the accessor and reader of class MyStack
    attr_reader :top, :size
    attr_accessor :top, :size
    def initialize() 
        self.top = nil
        self.size = 0
    end

    #  Add new element into stack
    def push(element) 
        #  Create new node
        node = StackNode.new(element)
        node.next = self.top
        #  new node is new top
        self.top = node
        #  Increase the size
        self.size += 1
    end

    #  Remove top element of the stack
    def pop() 
        if (self.top != nil) 
            #  next node is new top
            self.top = self.top.next
            #  Reduce size
            self.size -= 1
        end

    end

    #  Returns the status of empty or non empty stacks
    def isEmpty() 
        if (self.size > 0 && self.top != nil) 
            return false
        else
 
            return true
        end

    end

    #  Return top element of stack
    def peek() 
        if (self.isEmpty()) 
            return nil
        end

        return self.top.element
    end

end

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

    #  Display preorder view of binary tree
    def preorder() 
        if (self.root != nil) 
            #  Make new stack
            s = MyStack.new()
            node = self.root
            #  Display tree element
            while (!s.isEmpty() || node != nil) 
                if (node != nil) 
                    #  Display node value
                    print(" ", node.data)
                    #  Add current node
                    s.push(node)
                    #  Visit to left subtree
                    node = node.left
                else
 
                    #  When node is null
                    #  Get stack top element
                    node = s.peek()
                    #  Remove top element of the stack
                    s.pop()
                    #  Visit to left subtree of current node
                    node = node.right
                end

            end

        else
 
            print("Empty Linked List\n")
        end

    end

end

def main() 
    #  Create new tree
    tree = BinaryTree.new()
    #    Binary Tree
    #    -------------
    #          17
    #        /    \
    #      11      21
    #     / \     /  \
    #    1   39  10   2
    #       /
    #      40
    #  Add Tree Node
    tree.root = TreeNode.new(17)
    tree.root.left = TreeNode.new(11)
    tree.root.right = TreeNode.new(21)
    tree.root.right.right = TreeNode.new(2)
    tree.root.right.left = TreeNode.new(10)
    tree.root.left.left = TreeNode.new(1)
    tree.root.left.right = TreeNode.new(39)
    tree.root.left.right.left = TreeNode.new(40)
    #  Display Tree Node
    tree.preorder()
end

main()

Output

 17 11 1 39 40 21 10 2
// Scala Program
// Preorder traversal without recursion
// Using stack

// Binary Tree node
class TreeNode(var data: Int,
    var left: TreeNode,
        var right: TreeNode)
{
    // Make a tree node
    def this(data: Int)
    {
        // Set node data
        this(data, null, null);
    }
}
class StackNode(var element: TreeNode,
    var next: StackNode)
{
    def this(element: TreeNode)
    {
        this(element, null);
    }
}
// Stack Class
class MyStack(var top: StackNode,
    var size: Int)
{
    def this()
    {
        this(null, 0);
    }
    // Add new element into stack
    def push(element: TreeNode): Unit = {
        // Create new node
        var node: StackNode = new StackNode(element);
        node.next = this.top;
        // new node is new top
        this.top = node;
        // Increase the size
        this.size += 1;
    }
    // Remove top element of the stack
    def pop(): Unit = {
        if (this.top != null)
        {
            // next node is new top
            this.top = this.top.next;
            // Reduce size
            this.size -= 1;
        }
    }
    // Returns the status of empty or non empty stacks
    def isEmpty(): Boolean = {
        if (this.size > 0 && this.top != null)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    // Return top element of stack
    def peek(): TreeNode = {
        if (isEmpty())
        {
            return null;
        }
        return this.top.element;
    }
}
class BinaryTree(var root: TreeNode)
{
    def this()
    {
        this(null);
    }
    // Display preorder view of binary tree
    def preorder(): Unit = {
        if (this.root != null)
        {
            // Make new stack
            var s: MyStack = new MyStack();
            var node: TreeNode = this.root;
            // Display tree element
            while (!s.isEmpty() || node != null)
            {
                if (node != null)
                {
                    // Display node value
                    print(" " + node.data);
                    // Add current node
                    s.push(node);
                    // Visit to left subtree
                    node = node.left;
                }
                else
                {
                    // When node is null
                    // Get stack top element
                    node = s.peek();
                    // Remove top element of the stack
                    s.pop();
                    // Visit to left subtree of current node
                    node = node.right;
                }
            }
        }
        else
        {
            print("Empty Linked List\n");
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        // Create new tree
        var tree: BinaryTree = new BinaryTree();
        /*
            Binary Tree
            -------------
                  17
                /    \
              11      21
             / \     /  \
            1   39  10   2
               /
              40
        */
        // Add Tree Node
        tree.root = new TreeNode(17);
        tree.root.left = new TreeNode(11);
        tree.root.right = new TreeNode(21);
        tree.root.right.right = new TreeNode(2);
        tree.root.right.left = new TreeNode(10);
        tree.root.left.left = new TreeNode(1);
        tree.root.left.right = new TreeNode(39);
        tree.root.left.right.left = new TreeNode(40);
        // Display Tree Node
        tree.preorder();
    }
}

Output

 17 11 1 39 40 21 10 2
// Swift 4 Program
// Preorder traversal without recursion
// Using stack

// Binary Tree node
class TreeNode
{
    var data: Int;
    var left: TreeNode? ;
    var right: TreeNode? ;
    // Make a tree node
    init(_ data: Int)
    {
        // Set node data
        self.data = data;
        self.left = nil;
        self.right = nil;
    }
}
class StackNode
{
    var element: TreeNode? ;
    var next: StackNode? ;
    init(_ element: TreeNode? )
    {
        self.element = element;
        self.next = nil;
    }
}
// Stack Class
class MyStack
{
    var top: StackNode? ;
    var size: Int;
    init()
    {
        self.top = nil;
        self.size = 0;
    }
    // Add new element into stack
    func push(_ element: TreeNode? )
    {
        // Create new node
        let node: StackNode = StackNode(element);
        node.next = self.top;
        // new node is new top
        self.top = node;
        // Increase the size
        self.size += 1;
    }
    // Remove top element of the stack
    func pop()
    {
        if (self.top  != nil)
        {
            // next node is new top
            self.top = self.top!.next;
            // Reduce size
            self.size -= 1;
        }
    }
    // Returns the status of empty or non empty stacks
    func isEmpty() -> Bool
    {
        if (self.size > 0 && self.top  != nil)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    // Return top element of stack
    func peek() -> TreeNode?
    {
        if (self.isEmpty())
        {
            return nil;
        }
        return self.top!.element;
    }
}
class BinaryTree
{
    var root: TreeNode? ;
    init()
    {
        self.root = nil;
    }
    // Display preorder view of binary tree
    func preorder()
    {
        if (self.root  != nil)
        {
            // Make new stack
            let s: MyStack = MyStack();
            var node: TreeNode? = self.root;
            // Display tree element
            while (!s.isEmpty() || node  != nil)
            {
                if (node  != nil)
                {
                    // Display node value
                    print(" ", node!.data, terminator: "");
                    // Add current node
                    s.push(node);
                    // Visit to left subtree
                    node = node!.left;
                }
                else
                {
                    // When node is null
                    // Get stack top element
                    node = s.peek();
                    // Remove top element of the stack
                    s.pop();
                    // Visit to left subtree of current node
                    node = node!.right;
                }
            }
        }
        else
        {
            print("Empty Linked List");
        }
    }
}
func main()
{
    // Create new tree
    let tree: BinaryTree = BinaryTree();
    /*
        Binary Tree
        -------------
              17
            /    \
          11      21
         / \     /  \
        1   39  10   2
           /
          40
    */
    // Add Tree Node
    tree.root = TreeNode(17);
    tree.root!.left = TreeNode(11);
    tree.root!.right = TreeNode(21);
    tree.root!.right!.right = TreeNode(2);
    tree.root!.right!.left = TreeNode(10);
    tree.root!.left!.left = TreeNode(1);
    tree.root!.left!.right = TreeNode(39);
    tree.root!.left!.right!.left = TreeNode(40);
    // Display Tree Node
    tree.preorder();
}
main();

Output

  17  11  1  39  40  21  10  2
// Kotlin Program
// Preorder traversal without recursion
// Using stack

// Binary Tree node
class TreeNode
{
    var data: Int;
    var left: TreeNode ? ;
    var right: TreeNode ? ;
    // Make a tree node
    constructor(data: Int)
    {
        // Set node data
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
class StackNode
{
    var element: TreeNode ? ;
    var next: StackNode ? ;
    constructor(element: TreeNode ? )
    {
        this.element = element;
        this.next = null;
    }
}
// Stack Class
class MyStack
{
    var top: StackNode ? ;
    var size: Int;
    constructor()
    {
        this.top = null;
        this.size = 0;
    }
    // Add new element into stack
    fun push(element: TreeNode ? ): Unit
    {
        // Create new node
        val node: StackNode = StackNode(element);
        node.next = this.top;
        // new node is new top
        this.top = node;
        // Increase the size
        this.size += 1;
    }
    // Remove top element of the stack
    fun pop(): Unit
    {
        if (this.top != null)
        {
            // next node is new top
            this.top = this.top?.next;
            // Reduce size
            this.size -= 1;
        }
    }
    // Returns the status of empty or non empty stacks
    fun isEmpty(): Boolean
    {
        if (this.size > 0 && this.top != null)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    // Return top element of stack
    fun peek(): TreeNode ?
    {
        if (this.isEmpty())
        {
            return null;
        }
        return this.top?.element;
    }
}
class BinaryTree
{
    var root: TreeNode ? ;
    constructor()
    {
        this.root = null;
    }
    // Display preorder view of binary tree
    fun preorder(): Unit
    {
        if (this.root != null)
        {
            // Make new stack
            val s: MyStack = MyStack();
            var node: TreeNode ? = this.root;
            // Display tree element
            while (!s.isEmpty() || node != null)
            {
                if (node != null)
                {
                    // Display node value
                    print(" " + node.data);
                    // Add current node
                    s.push(node);
                    // Visit to left subtree
                    node = node.left;
                }
                else
                {
                    // When node is null
                    // Get stack top element
                    node = s.peek();
                    // Remove top element of the stack
                    s.pop();
                    // Visit to left subtree of current node
                    node = node?.right;
                }
            }
        }
        else
        {
            print("Empty Linked List\n");
        }
    }
}
fun main(args: Array < String > ): Unit
{
    // Create new tree
    val tree: BinaryTree = BinaryTree();
    /*
        Binary Tree
        -------------
              17
            /    \
          11      21
         / \     /  \
        1   39  10   2
           /
          40
    */
    // Add Tree Node
    tree.root = TreeNode(17);
    tree.root?.left = TreeNode(11);
    tree.root?.right = TreeNode(21);
    tree.root?.right?.right = TreeNode(2);
    tree.root?.right?.left = TreeNode(10);
    tree.root?.left?.left = TreeNode(1);
    tree.root?.left?.right = TreeNode(39);
    tree.root?.left?.right?.left = TreeNode(40);
    // Display Tree Node
    tree.preorder();
}

Output

 17 11 1 39 40 21 10 2

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