Iterative Approach Of Inorder tree traversal

Iterative Approach Of Inorder tree traversal

  August 26, 2017    

---

Explanation:

Here i am using Stack to store node so that when i pop , i will get last node and i will print and push all its right nodes that such that it will follow inorder property

Code:

void inOrder(Node root) {
Stack<Node> s=new Stack<>();
    while(root!=null)
    {
        s.push(root);
        root=root.left;
    }
    while(!s.isEmpty())
    {
        Node temp=s.pop();
        System.out.print(temp.data+" ");
        if(temp.right!=null)
        {
            s.add(temp.right);
            temp=temp.right;
            while(temp.left!=null)
            {
                s.add(temp.left);
                temp=temp.left;
            }
        }
    }
}


Approach 2: 

void inOrder(Node root) {
    Deque<Node> stack = new ArrayDeque<Node>();
    while(!stack.isEmpty() || root!=null){
        if(root!=null){
            stack.push(root);
            root = root.left;
        }else{
            root = stack.pop();
            System.out.print(root.data+" ");
            root = root.right;
        }
    }

}