What is the problem with this InOrder Traversal of Binary Tree?

Question

I implemented BinaryTree using java and tried to implement InOrder Traversal. I dry run the code on the copy in that case it works well but when I am running it on my IDE I am getting Infinite Loop. But why? Please help.

 class BinaryTree{
    
    class Node{
    
            private int data;
            private Node left, right;
            public Node(int data)
            {
                this.data = data;
                left=null;
                right=null;}
}
    public void inOrderTraversal(Node root)
            {
                Stack<Node> stack = new Stack<>();
                Node temp = root;
                stack.push(root);
                while(!stack.isEmpty())
                {
                    temp = stack.peek();
                    if(temp.left!=null)
                    {
                        stack.push(temp.left);
                    }
                    else
                    {
                        temp = stack.pop();
                        System.out.print(temp.data+" ");
                        if(temp.right!=null)
                        {
                            stack.push(temp.right);
                        }
                    }
                }
            }
    
    public static void main(String[] args) {
    
            Node one = new Node(1);
            Node two = new Node (2);
            Node three = new Node(3);
            Node four = new Node(4);
            Node five = new Node(5);
            Node six = new Node(6);
            one.left = two;
            one.right = three;
            two.left = four;
            two.right = five;
            three.left = six
    
            BinaryTrees bn = new BinaryTrees();
            bn.inOrderTraversal(one);
        }
}

Answer 1

To solve the above-mentioned problems we can do the implementation using a queue and a stack here.

public void inOrderTraversal(Node root) {
        Stack<Node> stack = new Stack<>();
        Queue<Node> out = new LinkedList<>();
        Node temp = root;
        stack.push(root);
        while (!stack.isEmpty()) {
            temp = stack.peek();
            if (temp.left != null && !temp.left.visited) {
                stack.push(temp.left);
            } else {
                temp = stack.pop();
                temp.visited = true;
                out.offer(temp);

                if (temp.right != null && !temp.right.visited) {
                    stack.push(temp.right);
                }
            }
        }
        while(!out.isEmpty())
        {
            Node tempo = out.poll();
            System.out.print(tempo.data+" ");
            tempo.visited=false;
        }
    }

This is the proper solution.

Answer 2

Your code starts with Node root equal to one. To the left of one is two, and to the left of two is four. Your traversal pushes two then four to the stack before the else condition is taken. Then you pop four, and since four has nothing on the right your while loop starts over. But the top of the stack is now two. To the left of two is still four, so you push four on the stack and thus your infinite loop starts.

You need a way to indicate Nodes that have already been visited. If you truly must use a stack, you should add a new attribute to your Node class such as private boolean visited and initialize it to false. After each temp = stack.pop() you would then need to set temp.visited = True, and only push onto the stack Nodes that have not been visited. Such as this:

class Node {
    private int data;
    private Node left, right;
    private boolean visited;
    public Node(int data) {
        this.data = data;
        left = null;
        right = null;
        visited = false;
    }
}

public void inOrderTraversal(Node root) {
    Stack<Node> stack = new Stack<>();
    Node temp = root;
    stack.push(root);
    while(!stack.isEmpty()) {
        temp = stack.peek();
        if(temp.left != null && !temp.left.visited) {
            stack.push(temp.left);
        } 
        else {
            temp = stack.pop();
            temp.visited = true;
            System.out.print(temp.data + " ");
            
            if(temp.right != null && !temp.right.visited) {
                stack.push(temp.right);
            }
        }
    }
}

A much simpler solution is to use recursion:

public void inOrderTraveralRecursive(Node node) {
    if (node == null) {
        return;
    }
    inOrderTraveralRecursive(node.left);
    System.out.print(node.data + " ");
    inOrderTraveralRecursive(node.right);
}