Binary tree throwing stack overflow exception while inorder traversing

Question

I am learning data structures and came across a pbm which I cannot solve. Can anyone help out here ?

I have created a TreeNode Class. In the same package I have created another class. this class has two methods . One does inorder traversing and there is another method(making a new binary tree from the existing) . I called the inorder traversing which worked fine. But If I call the inorder traversing method after my other method , I am getting exceptions.

The other method creates a new binary tree , but it is independent of inorder traversing method

public class TreeNode {
     public int val;
     public TreeNode left;
     public TreeNode right;
     TreeNode(int x) { val = x; }
}

In the same package I created another class.

package BST;
public class Check {
    TreeNode curr;
    TreeNode prev;

public void orderTraversal( TreeNode curr1) {

        if(curr1 == null)
            return;

        orderTraversal(curr1.left);

        if(curr == null ) {
            curr = curr1;
            prev = curr1;
        }
        else {
            prev.right = curr1;
            prev = curr1;
        }

        orderTraversal(curr1.right);
    }

    public static void main(String[] args) {
            // TODO Auto-gene`enter code here`rated method stub

        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.right = new TreeNode(15);

        Check check = new Check();  
        check.inOrder1(root);
        check.orderTraversal(root);
        check.inOrder1(root);
    }
    public  void inOrder1(TreeNode root) {
        if(root !=  null) {
            inOrder1(root.left); 
            System.out.printf("%d ",root.val);
            inOrder1(root.right);
        }

    }

}

When running the program , I am getting an exception in the method in the second call of inOrder1 . 

at sun.nio.cs.UTF_8.updatePositions(Unknown Source)
    at sun.nio.cs.UTF_8.access$200(Unknown Source)
    at sun.nio.cs.UTF_8$Encoder.encodeArrayLoop(Unknown Source)
    at sun.nio.cs.UTF_8$Encoder.encodeLoop(Unknown Source)
    at java.nio.charset.CharsetEncoder.encode(Unknown Source)
    at sun.nio.cs.StreamEncoder.implWrite(Unknown Source)
    at sun.nio.cs.StreamEncoder.write(Unknown Source)
    at java.io.OutputStreamWriter.write(Unknown Source)
    at java.io.BufferedWriter.flushBuffer(Unknown Source)
    at java.io.PrintStream.write(Unknown Source)
    at java.io.PrintStream.print(Unknown Source)
    at java.io.PrintStream.append(Unknown Source)

I know java works by pass by value. And the second method is referring only the instance variables. If I comment out check.orderTraversal(root) the second call to InOrder1 is working fine. I cant figure out why is it so ? Can anyone please help?

Thanks!

Answer 1

In your method orderTraversal you are modifying your tree at the line

prev.right = curr1;

That's your error. I don't really know what you are intending to do there, but you should not modify your tree in a tree traversal.

You said

the second method is referring only the instance variables

But when you do prev = curr1, your instance variable prev points to a node in the tree. Then when you do prev.right = curr1 you modify the node that prevpoints to.

Because you modify your tree, you create a circular reference. The node 3 has the node 9 as his left child, but the node 9 has 3 again (his own parent) as his left child. This is not a tree anymore, and that's why you have an infinite number of calls the second time you call inOrder1 which ends in a StackOverflowError.

By the way, this could be easily seen by using a debugger, I suggest you to have a look at this page.