# Inorder Tree Traversal Without recursion

In inorder tree traversal , left subtree is visited first , then the root and at last right subtree.Inorder Traversal of a binary search tree gives the sequence in non decreasing order In this article inorder traversal is performed using stack. And it is the obvious way to traverse tree without recursion.

## Steps to find inorder traversal without recursion:

• Step 1: Create an temporary variable and an empty stack of Node type with initial value null. Push the element value to stack and set  temp= temp.left until temp is null .Now stack become , Stack -> 2,3,5.
• Step 2: pop the element from the stack and assign it to temp variable and print it i.e print 2.Now stack become Stack->3,5. pop again and print it i.e. 3.Now stack become , Stack->5.
• step 3: push 4 to stack and make temp null. Stack-> 4,5.
• Step 4: pop 4 from the stack and print it .Now Stack->5. pop 5 from the stack and print it, so stack become Stack->null.
• Step 5: push 7 to stack and make temp null. So Stack become Stack->7.
• Step 6: pop 7 and print it . Now traversal is complete as stack is empty and temp is null.

## Algorithm

1. If root is null , simply return .
2. else , Create an empty stack  and initalize temp with root.
3. Push the temp to stack and set  temp=temp.left until temp is null.
4. Pop the top element from the stack and print it . Set temp=temp.right and goto step 3.
5. Until current become null and stack become empty.Then, we are done with our traversal.

## CODE FOR INORDER TRAVERSAL WITHOUT RECURSION

//Inorder Traversal without Recursion

/*Node class containing left and right child of current nod e and key value.*/

import java.util.*;

class Node{

int value;
Node left,right;
public Node(int value)
{
this.value=value;
left=null;
right=null;
}
}

class Inorder{

Node root; //root of the tree
public Inorder(){
root=null;
}

/*function for Inorder traversal of the tree*/
public void inorder()
{
if(root ==null)
return ;
Node temp=null;
Stack<Node> stack=new Stack<Node>(); //Creating an empty Stack
for(temp=root; stack.size()>0 || temp!=null ;temp=temp.right)
{
/*loop until we are on the left most node of the current node */
while(temp!=null)
{
stack.push(temp);  //inserting an element into stack
temp=temp.left;
}
/* removing the top element from the stack */
temp=stack.pop();
System.out.print(temp.value+" ");
}
}

public static void main(String[] args)
{
Inorder t=new Inorder();
t.root=new Node(5);
t.root.left=new Node(3);
t.root.right=new Node(7);
t.root.left.left=new Node(2);
t.root.left.right=new Node(4);
t.inorder();
}

}

2 3 4 5 7

O(n)

O(n)