# 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. ## Example For Inorder Traversal 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();     } }`

## Output:

`2 3 4 5 7`

O(n)

O(n)