Inorder Tree Traversal of a Binary Tree

There are two standard solution to traversal of binary tree in inorder form. First is recursion and second is iterative approach using stack. In this post view both of solution. Before traversal of tree in in-order form that is important to know about what will be the result of inorder traversal of any tree.

Inorder Traversal of Binary Tree

Note that nodes are print from left to right in a sequence. That is also indicates the form of,(L R' R). Here L is for left, (R') for root (current node) and R for right.

Recursive Solution

That is simplest method to traversal tree using system stack (recursion).

1) In this process start of root node of tree.

2) And check it current node value is NULL or not. When that is not NULL then visit left sub tree (left child node). Again repeat this process until current node are not NULL.

3) When current node is NULL in this case current execution are back to previous recursively function. In this time we are printed this node value and repeted step 4.

4) When we are printed node value, after that visit right child (right subtree) of current node. After that repeat the step of 2 and 3.

Here given code implementation process.

/* 
  Java Program 
  inorder 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 Inorder view of binary tree
    public void inorder(TreeNode node)
    {
        if (node != null)
        {
            // Visit left subtree
            inorder(node.left);
            //Print node value
            System.out.print("  " + node.data);
            // Visit right subtree
            inorder(node.right);
        }
    }
    public static void main(String[] args)
    {
        // Create new tree
        BinaryTree tree = new BinaryTree();
        /*   
            Make A Binary Tree
            ----------------
                15
               /  \
              24   54
             /    /  \
            35   62   13
         */
        // Add tree TreeNode
        tree.root = new TreeNode(15);
        tree.root.left = new TreeNode(24);
        tree.root.right = new TreeNode(54);
        tree.root.right.right = new TreeNode(13);
        tree.root.right.left = new TreeNode(62);
        tree.root.left.left = new TreeNode(35);
        // Display Tree Node
        tree.inorder(tree.root);
    }
}

Output

  35  24  15  62  54  13
/*
  C Program 
  Inorder Tree Traversal of a Binary Tree
*/
#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 Inorder view of binary tree
void inorder(struct TreeNode *node)
{
    if (node != NULL)
    {
        inorder(node->left);
        // Print node value
        printf("  %d", node->data);
        inorder(node->right);
    }
}
int main()
{
    struct BinaryTree *tree = newTree();
    /*
        Create Binary Tree
        -------------------
            15
           /  \
          24   54
         /    /  \
        35   62   13
    */
    // Add tree node
    tree->root = getNode(15);
    tree->root->left = getNode(24);
    tree->root->right = getNode(54);
    tree->root->right->right = getNode(13);
    tree->root->right->left = getNode(62);
    tree->root->left->left = getNode(35);
    // Display tree node
    inorder(tree->root);
    
    return 0;
}

Output

  35  24  15  62  54  13
// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program 
  inorder 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 Inorder view of binary tree
    void inorder(TreeNode *node)
    {
        if (node != NULL)
        {
            // Visit left subtree
            this->inorder(node->left);
            // Print node value
            cout << "  " << node->data;
            // Visit right subtree
            this->inorder(node->right);
        }
    }
};
int main()
{
    // Create new tree
    BinaryTree *tree = new BinaryTree();
    /*
        Make A Binary Tree
        ----------------
            15
           /  \
          24   54
         /    /  \
        35   62   13
    */
    // Add tree TreeNode
    tree->root = new TreeNode(15);
    tree->root->left = new TreeNode(24);
    tree->root->right = new TreeNode(54);
    tree->root->right->right = new TreeNode(13);
    tree->root->right->left = new TreeNode(62);
    tree->root->left->left = new TreeNode(35);
    // Display Tree Node
    tree->inorder(tree->root);
    return 0;
}

Output

  35  24  15  62  54  13
package main
import "fmt"
/* 
  Go Program 
  inorder 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 Inorder view of binary tree
func(this BinaryTree) inorder(node * TreeNode) {
    if node != nil {
        // Visit left subtree
        this.inorder(node.left)
        // Print node value
        fmt.Print("  ", node.data)
        // Visit right subtree
        this.inorder(node.right)
    }
}
func main() {
    // Create new tree
    var tree * BinaryTree = getBinaryTree()
    /*
        Make A Binary Tree
        ----------------
            15
           /  \
          24   54
         /    /  \
        35   62   13
    */
    // Add tree TreeNode
    tree.root = getTreeNode(15)
    tree.root.left = getTreeNode(24)
    tree.root.right = getTreeNode(54)
    tree.root.right.right = getTreeNode(13)
    tree.root.right.left = getTreeNode(62)
    tree.root.left.left = getTreeNode(35)
    // Display Tree Node
    tree.inorder(tree.root)
}

Output

  35  24  15  62  54  13
// Include namespace system
using System;
/* 
  Csharp Program 
  inorder 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 Inorder view of binary tree
    public void inorder(TreeNode node)
    {
        if (node != null)
        {
            // Visit left subtree
            this.inorder(node.left);
            // Print node value
            Console.Write("  " + node.data);
            // Visit right subtree
            this.inorder(node.right);
        }
    }
    public static void Main(String[] args)
    {
        // Create new tree
        BinaryTree tree = new BinaryTree();
        /*
            Make A Binary Tree
            ----------------
                15
               /  \
              24   54
             /    /  \
            35   62   13
        */
        // Add tree TreeNode
        tree.root = new TreeNode(15);
        tree.root.left = new TreeNode(24);
        tree.root.right = new TreeNode(54);
        tree.root.right.right = new TreeNode(13);
        tree.root.right.left = new TreeNode(62);
        tree.root.left.left = new TreeNode(35);
        // Display Tree Node
        tree.inorder(tree.root);
    }
}

Output

  35  24  15  62  54  13
<?php
/* 
  Php Program 
  inorder 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 Inorder view of binary tree
    public  function inorder($node)
    {
        if ($node != NULL)
        {
            // Visit left subtree
            $this->inorder($node->left);
            // Print node value
            echo("  ".$node->data);
            // Visit right subtree
            $this->inorder($node->right);
        }
    }
}

function main()
{
    // Create new tree
    $tree = new BinaryTree();
    /*
        Make A Binary Tree
        ----------------
            15
           /  \
          24   54
         /    /  \
        35   62   13
    */
    // Add tree TreeNode
    $tree->root = new TreeNode(15);
    $tree->root->left = new TreeNode(24);
    $tree->root->right = new TreeNode(54);
    $tree->root->right->right = new TreeNode(13);
    $tree->root->right->left = new TreeNode(62);
    $tree->root->left->left = new TreeNode(35);
    // Display Tree Node
    $tree->inorder($tree->root);
}
main();

Output

  35  24  15  62  54  13
/* 
  Node JS Program 
  inorder 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 Inorder view of binary tree
    inorder(node)
    {
        if (node != null)
        {
            // Visit left subtree
            this.inorder(node.left);
            // Print node value
            process.stdout.write("  " + node.data);
            // Visit right subtree
            this.inorder(node.right);
        }
    }
}

function main()
{
    // Create new tree
    var tree = new BinaryTree();
    /*
        Make A Binary Tree
        ----------------
            15
           /  \
          24   54
         /    /  \
        35   62   13
    */
    // Add tree TreeNode
    tree.root = new TreeNode(15);
    tree.root.left = new TreeNode(24);
    tree.root.right = new TreeNode(54);
    tree.root.right.right = new TreeNode(13);
    tree.root.right.left = new TreeNode(62);
    tree.root.left.left = new TreeNode(35);
    // Display Tree Node
    tree.inorder(tree.root);
}
main();

Output

  35  24  15  62  54  13
#  Python 3 Program 
#  inorder 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 Inorder view of binary tree
    def inorder(self, node) :
        if (node != None) :
            #  Visit left subtree
            self.inorder(node.left)
            #  Print node value
            print("  ", node.data, end = "")
            #  Visit right subtree
            self.inorder(node.right)
        
    

def main() :
    #  Create new tree
    tree = BinaryTree()
    #    Make A Binary Tree
    #    ----------------
    #        15
    #       /  \
    #      24   54
    #     /    /  \
    #    35   62   13
    #  Add tree TreeNode
    tree.root = TreeNode(15)
    tree.root.left = TreeNode(24)
    tree.root.right = TreeNode(54)
    tree.root.right.right = TreeNode(13)
    tree.root.right.left = TreeNode(62)
    tree.root.left.left = TreeNode(35)
    #  Display Tree Node
    tree.inorder(tree.root)

if __name__ == "__main__": main()

Output

   35   24   15   62   54   13
#  Ruby Program 
#  inorder 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 Inorder view of binary tree
    def inorder(node) 
        if (node != nil) 
            #  Visit left subtree
            self.inorder(node.left)
            #  Print node value
            print("  ", node.data)
            #  Visit right subtree
            self.inorder(node.right)
        end

    end

end

def main() 
    #  Create new tree
    tree = BinaryTree.new()
    #    Make A Binary Tree
    #    ----------------
    #        15
    #       /  \
    #      24   54
    #     /    /  \
    #    35   62   13
    #  Add tree TreeNode
    tree.root = TreeNode.new(15)
    tree.root.left = TreeNode.new(24)
    tree.root.right = TreeNode.new(54)
    tree.root.right.right = TreeNode.new(13)
    tree.root.right.left = TreeNode.new(62)
    tree.root.left.left = TreeNode.new(35)
    #  Display Tree Node
    tree.inorder(tree.root)
end

main()

Output

  35  24  15  62  54  13
/* 
  Scala Program 
  inorder 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 Inorder view of binary tree
    def inorder(node: TreeNode): Unit = {
        if (node != null)
        {
            // Visit left subtree
            inorder(node.left);
            // Print node value
            print("  " + node.data);
            // Visit right subtree
            inorder(node.right);
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        // Create new tree
        var tree: BinaryTree = new BinaryTree();
        /*
            Make A Binary Tree
            ----------------
                15
               /  \
              24   54
             /    /  \
            35   62   13
        */
        // Add tree TreeNode
        tree.root = new TreeNode(15);
        tree.root.left = new TreeNode(24);
        tree.root.right = new TreeNode(54);
        tree.root.right.right = new TreeNode(13);
        tree.root.right.left = new TreeNode(62);
        tree.root.left.left = new TreeNode(35);
        // Display Tree Node
        tree.inorder(tree.root);
    }
}

Output

  35  24  15  62  54  13
/* 
  Swift 4 Program 
  inorder 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 Inorder view of binary tree
    func inorder(_ node: TreeNode? )
    {
        if (node  != nil)
        {
            // Visit left subtree
            self.inorder(node!.left);
            // Print node value
            print("  ", node!.data, terminator: "");
            // Visit right subtree
            self.inorder(node!.right);
        }
    }
}
func main()
{
    // Create new tree
    let tree: BinaryTree = BinaryTree();
    /*
        Make A Binary Tree
        ----------------
            15
           /  \
          24   54
         /    /  \
        35   62   13
    */
    // Add tree TreeNode
    tree.root = TreeNode(15);
    tree.root!.left = TreeNode(24);
    tree.root!.right = TreeNode(54);
    tree.root!.right!.right = TreeNode(13);
    tree.root!.right!.left = TreeNode(62);
    tree.root!.left!.left = TreeNode(35);
    // Display Tree Node
    tree.inorder(tree.root);
}
main();

Output

   35   24   15   62   54   13
/* 
  Kotlin Program 
  inorder 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 Inorder view of binary tree
    fun inorder(node: TreeNode ? ): Unit
    {
        if (node != null)
        {
            // Visit left subtree
            this.inorder(node.left);
            // Print node value
            print("  " + node.data);
            // Visit right subtree
            this.inorder(node.right);
        }
    }
}
fun main(args: Array < String > ): Unit
{
    // Create new tree
    val tree: BinaryTree = BinaryTree();
    /*
        Make A Binary Tree
        ----------------
            15
           /  \
          24   54
         /    /  \
        35   62   13
    */
    // Add tree TreeNode
    tree.root = TreeNode(15);
    tree.root?.left = TreeNode(24);
    tree.root?.right = TreeNode(54);
    tree.root?.right?.right = TreeNode(13);
    tree.root?.right?.left = TreeNode(62);
    tree.root?.left?.left = TreeNode(35);
    // Display Tree Node
    tree.inorder(tree.root);
}

Output

  35  24  15  62  54  13

Iterative Solution

In iterative approach we can solve this problem using stack. Stack are main two operation push() and pop(). When find new binary tree nodes then this element are push to stack and when no new node are found then print top element of stack, and pop() remove to top element.

// Java Program 
// Inorder 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;
    }
}
class BinaryTree
{
    public TreeNode root;
    public BinaryTree()
    {
        // Set initial tree root to null
        this.root = null;
    }
    // Display Inorder view of binary tree
    public void inorder()
    {
        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)
                {
                    // 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();
                    // Display node value
                    System.out.print(" " + node.data);
                    // 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();
        /*   
            Construct Binary Tree
            -----------------------
                15
               /  \
              24   54
             /    /  \
            35   62   13
         */
        //Add tree node
        tree.root = new TreeNode(15);
        tree.root.left = new TreeNode(24);
        tree.root.right = new TreeNode(54);
        tree.root.right.right = new TreeNode(13);
        tree.root.right.left = new TreeNode(62);
        tree.root.left.left = new TreeNode(35);
        //Display Tree elements
        tree.inorder();
    }
}

Output

 35 24 15 62 54 13
/*
  C Program 
  Inorder 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 Inorder view of binary tree
void inorder(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)
            {
                // 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);
                // Display node value
                printf("%d  ", node->data);
                // 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();
    /*
        Create Binary Tree
        -------------------
            15
           /  \
          24   54
         /    /  \
        35   62   13
    */
    // Add tree node
    tree->root = getNode(15);
    tree->root->left = getNode(24);
    tree->root->right = getNode(54);
    tree->root->right->right = getNode(13);
    tree->root->right->left = getNode(62);
    tree->root->left->left = getNode(35);
    // Display Tree elements
    inorder(tree->root);
    return 0;
}

Output

35  24  15  62  54  13
// Include header file
#include <iostream>
using namespace std;
// C++ Program 
// Inorder 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 Inorder view of binary tree
    void inorder()
    {
        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)
                {
                    // 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();
                    // Display node value
                    cout << " " << node->data;
                    // 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();
    /* 
                Construct Binary Tree
                -----------------------
                    15
                   /  \
                  24   54
                 /    /  \
                35   62   13
             */
    //Add tree node
    tree->root = new TreeNode(15);
    tree->root->left = new TreeNode(24);
    tree->root->right = new TreeNode(54);
    tree->root->right->right = new TreeNode(13);
    tree->root->right->left = new TreeNode(62);
    tree->root->left->left = new TreeNode(35);
    //Display Tree elements
    tree->inorder();
    return 0;
}

Output

 35 24 15 62 54 13
package main
import "fmt"
// Go Program
// Inorder 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 Inorder view of binary tree
func(this BinaryTree) inorder() {
    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 {
                // 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()
                // Display node value
                fmt.Print(" ", node.data)
                // 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()
    /*
        Construct Binary Tree
        -----------------------
            15
           /  \
          24   54
         /    /  \
        35   62   13
    */
    //Add tree node
    tree.root = getTreeNode(15)
    tree.root.left = getTreeNode(24)
    tree.root.right = getTreeNode(54)
    tree.root.right.right = getTreeNode(13)
    tree.root.right.left = getTreeNode(62)
    tree.root.left.left = getTreeNode(35)
    //Display Tree elements
    tree.inorder()
}

Output

 35 24 15 62 54 13
// Include namespace system
using System;
// Csharp Program
// Inorder 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 Inorder view of binary tree
    public void inorder()
    {
        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)
                {
                    // 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();
                    // Display node value
                    Console.Write(" " + node.data);
                    // 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();
        /*
            Construct Binary Tree
            -----------------------
                15
               /  \
              24   54
             /    /  \
            35   62   13
        */
        //Add tree node
        tree.root = new TreeNode(15);
        tree.root.left = new TreeNode(24);
        tree.root.right = new TreeNode(54);
        tree.root.right.right = new TreeNode(13);
        tree.root.right.left = new TreeNode(62);
        tree.root.left.left = new TreeNode(35);
        //Display Tree elements
        tree.inorder();
    }
}

Output

 35 24 15 62 54 13
<?php
// Php Program
// Inorder 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 Inorder view of binary tree
    public  function inorder()
    {
        if ($this->root != NULL)
        {
            // Make new stack
            $s = new MyStack();
            $node = $this->root;
            // Display tree element
            while (!$s->isEmpty() || $node != NULL)
            {
                if ($node != NULL)
                {
                    // 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();
                    // Display node value
                    echo(" ".$node->data);
                    // 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();
    /*
        Construct Binary Tree
        -----------------------
            15
           /  \
          24   54
         /    /  \
        35   62   13
    */
    //Add tree node
    $tree->root = new TreeNode(15);
    $tree->root->left = new TreeNode(24);
    $tree->root->right = new TreeNode(54);
    $tree->root->right->right = new TreeNode(13);
    $tree->root->right->left = new TreeNode(62);
    $tree->root->left->left = new TreeNode(35);
    //Display Tree elements
    $tree->inorder();
}
main();

Output

 35 24 15 62 54 13
// Node JS Program
// Inorder 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 Inorder view of binary tree
    inorder()
    {
        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)
                {
                    // 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();
                    // Display node value
                    process.stdout.write(" " + node.data);
                    // 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();
    /*
        Construct Binary Tree
        -----------------------
            15
           /  \
          24   54
         /    /  \
        35   62   13
    */
    //Add tree node
    tree.root = new TreeNode(15);
    tree.root.left = new TreeNode(24);
    tree.root.right = new TreeNode(54);
    tree.root.right.right = new TreeNode(13);
    tree.root.right.left = new TreeNode(62);
    tree.root.left.left = new TreeNode(35);
    //Display Tree elements
    tree.inorder();
}
main();

Output

 35 24 15 62 54 13
#  Python 3 Program
#  Inorder 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 Inorder view of binary tree
    def inorder(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) :
                    #  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()
                    #  Display node value
                    print(" ", node.data, end = "")
                    #  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()
    #   Construct Binary Tree
    #   -----------------------
    #        15
    #       /  \
    #      24   54
    #     /    /  \
    #    35   62   13
    # Add tree node
    tree.root = TreeNode(15)
    tree.root.left = TreeNode(24)
    tree.root.right = TreeNode(54)
    tree.root.right.right = TreeNode(13)
    tree.root.right.left = TreeNode(62)
    tree.root.left.left = TreeNode(35)
    # Display Tree elements
    tree.inorder()

if __name__ == "__main__": main()

Output

  35  24  15  62  54  13
#  Ruby Program
#  Inorder 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 Inorder view of binary tree
    def inorder() 
        if (self.root != nil) 
            #  Make new stack
            s = MyStack.new()
            node = self.root
            #  Display tree element
            while (!s.isEmpty() || node != nil) 
                if (node != nil) 
                    #  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()
                    #  Display node value
                    print(" ", node.data)
                    #  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()
    #   Construct Binary Tree
    #   -----------------------
    #        15
    #       /  \
    #      24   54
    #     /    /  \
    #    35   62   13
    # Add tree node
    tree.root = TreeNode.new(15)
    tree.root.left = TreeNode.new(24)
    tree.root.right = TreeNode.new(54)
    tree.root.right.right = TreeNode.new(13)
    tree.root.right.left = TreeNode.new(62)
    tree.root.left.left = TreeNode.new(35)
    # Display Tree elements
    tree.inorder()
end

main()

Output

 35 24 15 62 54 13
// Scala Program
// Inorder 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 Inorder view of binary tree
    def inorder(): 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)
                {
                    // 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();
                    // Display node value
                    print(" " + node.data);
                    // 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();
        /*
            Construct Binary Tree
            -----------------------
                15
               /  \
              24   54
             /    /  \
            35   62   13
        */
        //Add tree node
        tree.root = new TreeNode(15);
        tree.root.left = new TreeNode(24);
        tree.root.right = new TreeNode(54);
        tree.root.right.right = new TreeNode(13);
        tree.root.right.left = new TreeNode(62);
        tree.root.left.left = new TreeNode(35);
        //Display Tree elements
        tree.inorder();
    }
}

Output

 35 24 15 62 54 13
// Swift 4 Program
// Inorder 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 Inorder view of binary tree
    func inorder()
    {
        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)
                {
                    // 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();
                    // Display node value
                    print(" ", node!.data, terminator: "");
                    // 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();
    /*
        Construct Binary Tree
        -----------------------
            15
           /  \
          24   54
         /    /  \
        35   62   13
    */
    //Add tree node
    tree.root = TreeNode(15);
    tree.root!.left = TreeNode(24);
    tree.root!.right = TreeNode(54);
    tree.root!.right!.right = TreeNode(13);
    tree.root!.right!.left = TreeNode(62);
    tree.root!.left!.left = TreeNode(35);
    //Display Tree elements
    tree.inorder();
}
main();

Output

  35  24  15  62  54  13
// Kotlin Program
// Inorder 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 Inorder view of binary tree
    fun inorder(): 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)
                {
                    // 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();
                    // Display node value
                    print(" " + node!!.data);
                    // 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();
    /*
        Construct Binary Tree
        -----------------------
            15
           /  \
          24   54
         /    /  \
        35   62   13
    */
    //Add tree node
    tree.root = TreeNode(15);
    tree.root?.left = TreeNode(24);
    tree.root?.right = TreeNode(54);
    tree.root?.right?.right = TreeNode(13);
    tree.root?.right?.left = TreeNode(62);
    tree.root?.left?.left = TreeNode(35);
    //Display Tree elements
    tree.inorder();
}

Output

 35 24 15 62 54 13

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