# Inorder traversal of binary tree using stack in scala

Scala program for Inorder traversal of binary tree using stack. Here problem description and explanation.

``````// Scala program for
// 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)
{
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 result
tree.inorder();
}
}``````

Output

`` 35 24 15 62 54 13``

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.