StackOverflow while adding elements to a BST java

Question

private Node put(Node x, Float longitude, Float latitude, String place, String address) {
    if (x == null)
        return new Node(longitude, latitude, place, address, 1);
    int cmpX = longitude.compareTo(x.longitude);
    int cmpY = latitude.compareTo(x.latitude);
    if (cmpX < 0 | (cmpX == 0 && cmpY < 0)) {
        if (x.left == null) { x.left = new Node(longitude, latitude, place, address, x.N);}
        else{x.left = put(x.left, longitude, latitude, place, address);}
    } else if (cmpX >= 0) {
        if (x.right == null) {  x.right = new Node(longitude, latitude, place, address, x.N);}
        else{x.right = put(x.right, longitude, latitude, place, address);}
    }
    x.N = 1 + size(x.left) + size(x.right);
    return x;
}

I have this code that I'm try to use to insert into a BST and it works for the first 3000 or so elements, before causing a StackOverFlow error. How do I prevent this from happening?

Answer 1

The reason that you encountered a StackOverflowError is that you inserted your items in an order that was already sorted. Let's see what happens in this case. I'll use integers, even though you have more complicated objects, for simplicity in seeing what happens.

After inserting 1:

Root(1)

After inserting 2:

Root(1)
    \
     (2)

After inserting 3:

Root(1)
    \
     (2)
      \
       (3)

After inserting n:

Root(1)
    \
     (2)
      \
       ...
        \
         (n)

You implemented put as a recursive method. Because of that, when you have added 3000 elements, and you're attempting to add a 3001st element, you need to recur 3000 times, and now there are 3000 copies of put on the call stack, about where you say it overflows.

You can convert put into an iterative method, using a while loop instead of recursion. This will eliminate the StackOverflowError, but it won't solve the root (so to speak) of the problem -- that your BST looks like a linked list.

You can submit your elements in a random order. It may look like this:

    Root(1123)
     /        \
   (799)       (2800)
   /  \       /     \
 (64) (999) (1599)   (2901)

It may not be properly balanced, but most likely it will not devolve into the linked list situation you have from inserting in sorted order.

You can perform rotations about a specific node when one branch gets too large compared to the other branch. If you're feeling adventurous, you can implement a red-black tree, a BST that uses rotations to keep the tree balanced "enough".