Java stackoverflow error on recursive function

Question

when I call this function, why there is a stackoverflow error? I have checked my terminal conditions but can not figure out where the problem is.

public static TreeNode buildTree(int t1, int t2, ListNode[] nodeArray) {     
    if(t1 == t2){
        TreeNode temp = new TreeNode(nodeArray[t1].val);
        temp.left = null;
        temp.right = null;
        return temp;
    }
    else if(t1 > t2){
        return null;
    }

    else{   
        TreeNode root = new TreeNode(nodeArray[(t1+t2)/2].val);
        root.left = buildTree(0,(t1+t2)/2-1,nodeArray);
        root.right = buildTree((t1+t2)/2+1,nodeArray.length-1,nodeArray);
        return root;
    }
}

The most likely situation is that you are allways going into the else part of your condition and end in an endless call of buildTree. — SomeJavaGuy
– SomeJavaGuy, Commented Oct 14, 2015 at 7:53

Eran · Accepted Answer · 2015-10-14 07:57:01Z

6

It looks like the recursive method should be working on a range between t1 and t2, so the recursive calls should be :

root.left = buildTree(t1,(t1+t2)/2-1,nodeArray);
root.right = buildTree((t1+t2)/2+1,t2,nodeArray);

Your current recursive calls never narrow the range (you always pass one range from 0 to the middle and another range from the middle to the end of nodeArray), so the recursion never ends.

edited Oct 14, 2015 at 7:57

answered Oct 14, 2015 at 7:54

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

paxdiablo · Accepted Answer · 2015-10-14 07:56:46Z

0

This is just Debugging 101.

Place the following line as the first in the method:

System.out.println("Entry, t1 = " + t1 + ", t2 = " + t2);

From that, you will be able to work out the flow.

answered Oct 14, 2015 at 7:56

paxdiablo

888k243 gold badges1.6k silver badges2k bronze badges

Comments

kumade · Accepted Answer · 2015-10-14 08:21:50Z

0

Simple example of calling Your method with an array [0, 1, 2, 3, 4] like buildTree(0, 4, array):

1    root = 2;
2    buildTree(0, 1);
3        root = 0;
4        buildTree(0, -1);
5            null;
6        buildTree(1, 4);
7            root = 2;
8            buildTree(0, 1); // endless recursion. see 2nd line call

answered Oct 14, 2015 at 8:21

kumade

5412 gold badges10 silver badges18 bronze badges

Collectives™ on Stack Overflow

Java stackoverflow error on recursive function

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related