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

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_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;
}
}
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
{
}
}
public static void main(String[] args)
{
// Create new tree
BinaryTree tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
15
/  \
24   54
/    /  \
35   62   13
*/
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++;
}
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
{
}
}
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;
}
}
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
*/
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
}
}
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 {
}
}
func main() {
// Create new tree
var tree * BinaryTree = getBinaryTree()
/*
Construct Binary Tree
-----------------------
15
/  \
24   54
/    /  \
35   62   13
*/
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;
}
}
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
{
}
}
public static void Main(String[] args)
{
// Create new tree
BinaryTree tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
15
/  \
24   54
/    /  \
35   62   13
*/
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;
}
}
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
{
}
}
}

function main()
{
// Create new tree
\$tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
15
/  \
24   54
/    /  \
35   62   13
*/
\$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;
}
}
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
{
}
}
}

function main()
{
// Create new tree
var tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
15
/  \
24   54
/    /  \
35   62   13
*/
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

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 :

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_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_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

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_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

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;
}
}
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
{
}
}
}
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
*/
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;
}
}
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
{
}
}
}
func main()
{
// Create new tree
let tree: BinaryTree = BinaryTree();
/*
Construct Binary Tree
-----------------------
15
/  \
24   54
/    /  \
35   62   13
*/
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;
}
}
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
{
}
}
}
fun main(args: Array < String > ): Unit
{
// Create new tree
val tree: BinaryTree = BinaryTree();
/*
Construct Binary Tree
-----------------------
15
/  \
24   54
/    /  \
35   62   13
*/
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.