Recursive tree construction and Stack Overflow Error

Question

I am trying to use a recursive method to create a binary search tree with 1,000,000 nodes, each containing a number from 0 to 1,000,000. The root must contain 500,000, with its left child containing 250,000 and right child containing 750,000. This pattern will continue with each node until all numbers are used. I need to then return the root to allow the program to search for a specific number. However, I keep getting a stack overflow error. When I change the numbers to 0 and 2 to test it on a smaller scale, it keeps returning the node with 2, rather than with 1. Any ideas?

public static BTNode treeMaker(int minimum, int maximum)
{
    int currentNum = (minimum + maximum)/2;
    BTNode node = new BTNode(currentNum, null, null);
    if(minimum == maximum)
        return node;
    else
    {
        node.setLeft(treeMaker(minimum, currentNum - 1));
        node.setRight(treeMaker(currentNum + 1, maximum));
        return node;
    }
}

Edit: Here is the BTNode class:

public class BTNode 
{
   private static int data;
   private static BTNode left, right;

   public BTNode(int newData, BTNode newLeft, BTNode newRight)
   {
       data = newData;
       left = newLeft;
       right = newRight;
   }

   public static BTNode getLeft()
   {
       return left;
   }

   public static BTNode getRight()
   {
       return right;
   }

   public static int getData()
   {
       return data;
   }

   public static void setLeft(BTNode newLeft)
   {
      left = newLeft;
   }

   public static void setRight(BTNode newRight)
   {
       right = newRight;
   }
}

On first glance it looks like you're missing { } around the `else` case, but actually it doesn't matter in this case, although it's obfuscated. — Bathsheba, Oct 12 '16 at 12:26
Oh yeah oops haha. I'll fix that really quick. Any suggestions on a fix for the error? — Frolf182, Oct 12 '16 at 12:29
I think we need to see more of the code; especially the `BTNode` constructor. — Bathsheba, Oct 12 '16 at 12:30
You are missing the case where minimum > maximum. This can happen for example when you call with (1, 2). This gives currentNum=1 and the next recursive call will be (1,0). — Henry, Oct 12 '16 at 12:33
Ok I have added that to my code, and the overflow error has stopped. However it now returns a node with the highest number, rather than the middle number (ie, 1,000,000 rather than 500,000). I'm not sure why though. I would think it would eventually return the root node. — Frolf182, Oct 12 '16 at 12:42
So you could simply be running out of stack space. http://stackoverflow.com/questions/12230474/how-many-function-calls-will-cause-stack-overflow — C.B., Oct 12 '16 at 12:45
The fields and methods in the `BTNode` class must not be static. — Henry, Oct 12 '16 at 12:51

score 0 · Answer 1 · answered Oct 12 '16 at 13:22

Couldn't get through the java.lang.StackOverflowError, but found the error for: it keeps returning on 2

You have defined fields (data, left, right) and functions at class level, whereas these should be defined at instance level. When you keep fields at class level, their values gets updated for every node and you get the last value being processed, which is 2.

Try following (fields are at instance level):

public class BTNode {

private int data;
private BTNode left;
private BTNode right;

private BTNode(int newData, BTNode newLeft, BTNode newRight) {
    data = newData;
    left = newLeft;
    right = newRight;
}

public BTNode getLeft() {
    return left;
}

public BTNode getRight() {
    return right;
}

public int getData() {
    return data;
}

public void setLeft(BTNode newLeft) {
    left = newLeft;
}

public void setRight(BTNode newRight) {
    right = newRight;
}

public static BTNode getBT(int minimum, int maximum) {
    int currentNum = (minimum + maximum) / 2;
    BTNode node = new BTNode(currentNum, null, null);
    if (minimum == maximum)
        return node;
    else {
        node.setLeft(BTNode.getBT(minimum, currentNum - 1));
        node.setRight(BTNode.getBT(currentNum + 1, maximum));
        return node;
    }
}

public static void main(String[] args) {
    BTNode node = BTNode.getBT(0, 2);
    System.out.println(node.getData());
}

}

Recursive tree construction and Stack Overflow Error

1 Answers1