Java - StackOverFlowError

Question

I need some help for this.

First I have a class BinarySearchTree

import java.util.ArrayList;
import java.util.List;

public class BinarySearchTree<E extends Comparable<? super E>> {

private BSTNode<E> root;
private int size;

// root ==null iff size == 0

public BinarySearchTree() {
    root = null;
    size = 0;
}


public boolean add(E value) {
    int oldSize = size;
    root = addHelper(root, value);
    return oldSize != size;
}

private BSTNode<E> addHelper(BSTNode<E> n, E val) {
    if (n == null) {
        n = new BSTNode<E>(null, val, null);
        size++;
    } else {
        int diff = val.compareTo(n.getData());
        if (diff < 0)
            n.setLeft(addHelper(n.getLeft(), val));
        else if (diff > 0)
            n.setRight(addHelper(n.getRight(), val));
    }
    return n;
}


public boolean remove(E value) {
    int oldSize = size;
    root = removeHelp(root, value);
    return oldSize != size;
}

// helper method for remove
private BSTNode<E> removeHelp(BSTNode<E> n, E val) {
    if (n != null) {
        int diff = val.compareTo(n.getData());
        if (diff < 0)
            n.setLeft(removeHelp(n.getLeft(), val)); // traverse the left
                                                     // side
        else if (diff > 0)
            n.setRight(removeHelp(n.getRight(), val)); // traverse right
                                                       // side
        else // if value is found
        {
            size--;
            if (n.getLeft() == null && n.getRight() == null) // if value
                                                             // contained in
                                                             // leaf, just
                                                             // make nul;
                n = null;
            else if (n.getRight() == null) // single child to left
                n = n.getLeft(); // move the child up to replace removed
                                 // node
            else if (n.getLeft() == null)
                n = n.getRight();
            else // two children, replace value with max of left subtree -
                 // it will not have a right subtree
            {
                n.setData(getMax(n.getLeft()));
                // now remove max of left subtree from its previous position
                n.setLeft(removeHelp(n.getLeft(), n.getData()));
                // add 1 back to size since size will be decremented from
                // this 2nd removal
                size++;
            }

        }
    }
    return n;
}

// helper method to find Max of a subtree
private E getMax(BSTNode<E> n) {
    while (n.getRight() != null)
        n = n.getRight();
    return n.getData();
}


public boolean isPresent(E value) {
    assert value != null : "Precondition failed: value != null";
    if (root == null)
        return false;
    return isPresentHelp(root, value);

}

public boolean isPresentHelp(BSTNode<E> n, E item) {
    if (n == null)
        return false;
    else {
        E temp = n.getData();
        // if item to search is greater than node, traverse right
        if (temp.compareTo(item) < 0)
            return isPresentHelp(n.getRight(), item);
        else if (temp.compareTo(item) > 0)
            return isPresentHelp(n.getLeft(), item);
        else
            return true;
    }
}


public int size() {
    return size;
}


public int height() {
    return heightHelper(root);
}

public int heightHelper(BSTNode<E> n) {
    int tempLeft, tempRight;
    if(n == null) 
        return -1;
    tempLeft = 1 + heightHelper(n.getLeft());
    tempRight = 1 + heightHelper(n.getRight());
    if(tempLeft > tempRight)
        return tempLeft;
    else 
        return tempRight;
}


public List<E> getAll() {
    List<E> result = new ArrayList<E>();
    return getAllHelp(root, result);
}

public List<E> getAllHelp(BSTNode<E> n, List<E> result) {

    if (n != null) {
        // traverse left to lowest value
        getAllHelp(n.getLeft(), result);
        // add to arraylist if it can go left no further (smallest current
        // value)
        result.add(n.getData());
        // traverse right if can't go left anymore
        getAllHelp(n.getRight(), result);

    }
    return result;
}


public E max() {
    return getMax(root);
}


public E min() {
    return getMin(root);
}

private E getMin(BSTNode<E> n) {
    while (n.getLeft() != null)
        n = n.getLeft();
    return n.getData();
}


public boolean iterativeAdd(E data) {
    BSTNode<E> n = root;
    while (n != null) {
        if (n.getData().compareTo(data) > 0) {
            if (n.getLeft() == null) {
                n.setLeft(new BSTNode<E>(data));
                size++;
                return true;
            } else
                n = n.getLeft();
        } else if (n.getData().compareTo(data) < 0) {
            if (n.getRight() == null) {
                n.setRight(new BSTNode<E>(data));
                size++;
                return true;
            } else
                n = n.getRight();
        } else
            return false;
    }
    root = new BSTNode<E>(null, data, null);
    size++;
    return true;
}


public E get(int kth) {
    assert 0 <= kth && kth < size() : "Precondition failed: 0 <= kth < size()";
    // keep track of which index recursive call is on (or the kth element)
    int count[] = { 0 };
    return getHelp(kth, root, count);
}

public E getHelp(int nth, BSTNode<E> n, int[] count) {
    E result = null;
    if (n != null) {
        result = getHelp(nth, n.getLeft(), count);
        if (result == null) {
            if (count[0] == nth) {
                return n.getData();
            } else {
                count[0]++;
                result = getHelp(nth, n.getRight(), count);
            }
        }
    }
    return result;
}


public List<E> getAllLessThan(E value) {
    List<E> result = new ArrayList<E>();
    return getAllLessHelp(root, result, value);
}

public List<E> getAllLessHelp(BSTNode<E> n, List<E> result, E value) {
    if (n != null) {
        getAllLessHelp(n.getLeft(), result, value);
        if (n.getData().compareTo(value) < 0) {
            result.add(n.getData());
        }
        getAllLessHelp(n.getRight(), result, value);
    }
    return result;
}


public List<E> getAllGreaterThan(E value) {
    List<E> result = new ArrayList<E>();
    return getAllGreaterHelp(root, result, value);
}

// returns the BSTNode containing the value
public List<E> getAllGreaterHelp(BSTNode<E> n, List<E> result, E value) {
    if (n != null) {
        if (n.getData().compareTo(value) > 0) {
            getAllGreaterHelp(n.getLeft(), result, value);
            result.add(n.getData());
        }
        getAllGreaterHelp(n.getRight(), result, value);
    }
    return result;
}

public int numNodesAtDepth(int d) {
    return numNodesHelp(d, root, 0);
}

public int numNodesHelp(int d, BSTNode<E> n, int count) {
    count = 0;
    if (n != null) {
        if (d == 0)
            count++;
        else {
            count += numNodesHelp(d - 1, n.getLeft(), count);
            count += numNodesHelp(d - 1, n.getRight(), count);
        }
    }
    return count;
}


public void printTree() {
    printTree(root, "");
}

private void printTree(BSTNode<E> n, String spaces) {
    if (n != null) {
        printTree(n.getRight(), spaces + "  ");
        System.out.println(spaces + n.getData());
        printTree(n.getLeft(), spaces + "  ");
    }
}


private static class BSTNode<E extends Comparable<? super E>> {
    private E data;
    private BSTNode<E> left;
    private BSTNode<E> right;

    public BSTNode() {
        this(null);
    }

    public BSTNode(E initValue) {
        this(null, initValue, null);
    }

    public BSTNode(BSTNode<E> initLeft, E initValue, BSTNode<E> initRight) {
        data = initValue;
        left = initLeft;
        right = initRight;
    }

    public E getData() {
        return data;
    }

    public BSTNode<E> getLeft() {
        return left;
    }

    public BSTNode<E> getRight() {
        return right;
    }

    public void setData(E theNewValue) {
        data = theNewValue;
    }

    public void setLeft(BSTNode<E> theNewLeft) {
        left = theNewLeft;
    }

    public void setRight(BSTNode<E> theNewRight) {
        right = theNewRight;
    }
}
}

And the Tester Class

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.TreeSet;

public class BSTTester {

public static void main(String[] args) {
    // do the experiment
    experiment_1();
    experiment_2();
    experiment_3();
}

private static void experiment_1() {
    Random r = new Random();
    Stopwatch s = new Stopwatch();

    for (int n = 1000; n <= 1024000; n *= 2) {
        double avgTime = 0;
        int avgHeight = 0;
        int avgSize = 0;
        for (int index = 0; index < 10; index++) {
            BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
            s.start();
            for (int i = 0; i < n; i++) {
                b.add(r.nextInt());
            }
            s.stop();
            avgTime += s.time();
            avgHeight += b.height();
            avgSize += b.size();
        }
        System.out.println("Random: It took an average of " + avgTime / 10 + " seconds to add "
                        + n + " items to the BST.");
        System.out.println("Random: The tree has a height of " + avgHeight / 10
                        + " rows when it has " + n + " items.");
        System.out.println("Random: The tree has a size of " + avgSize / 10 + " items when "
                        + n + " supposed to be added");
        System.out.println(" ");
    }
}

private static void experiment_2() {
    Random r = new Random();
    Stopwatch s = new Stopwatch();

    for (int n = 1000; n <= 1024000; n *= 2) {
        double avgTime = 0;
        int avgSize = 0;
        for (int index = 0; index < 10; index++) {
            TreeSet<Integer> t = new TreeSet<Integer>();
            s.start();
            for (int i = 0; i < n; i++) {
                t.add(r.nextInt());
            }
            s.stop();
            avgTime += s.time();
            avgSize += t.size();
        }
        System.out.println("In Order TreeSet: It took an average of " + avgTime / 10
                        + " seconds to add " + n + " items to the BST.");
        System.out.println("In Order TreeSet: The tree has a size of " + avgSize / 10
                        + " items when " + n + " supposed to be added.");
        System.out.println(" ");
    }
}

private static void experiment_3() {
    Stopwatch s = new Stopwatch();

    for (int n = 1000; n <= 1024000; n *= 2) {
        double avgTime = 0;
        int avgHeight = 0;
        int avgSize = 0;
        for (int index = 0; index < 10; index++) {
            BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
            s.start();
            for (int i = 0; i < n; i++) {
                b.iterativeAdd(i);
            }
            s.stop();
            avgTime += s.time();
            avgHeight += b.height();
            avgSize += b.size();
        }
        System.out.println("In Order: It took an average of " + avgTime / 10
                        + " seconds to add " + n + " items to the BST.");
        System.out.println("In Order: The tree has a height of " + avgHeight / 10
                        + " rows when it has " + n + " items.");
        System.out.println("In Order: The tree has a size of " + avgSize / 10 + " items when "
                        + n + " supposed to be added.");
        System.out.println(" ");
    }
}

private static void showTestResults(boolean passed, int testNum) {
    if (passed)
        System.out.println("test " + testNum + " passed.");
    else
        System.out.println("test " + testNum + " failed.");
}
}

So basically the experiment 1 is to add N random numbers to the Binary Search Tree, record the time it takes, height of the tree, size of the tree. experiment 2 does the same thing but with java TreeSet experiment 3 is to add N sorted numbers to the Binary Search Tree

with N = 2,000, 4,000, 8,000, 16,000, 32,000, 64,000, 128,00, 256,000, 512,000, and 1,024,000

the thing is, exp1 and exp2 run fine. But when exp3 runs, I get the StackOverflowError when adding about 32000 items. The height method did well with exp1, exp2, don't know why it causes error in exp3. The same when I use add method, not iterativeAdd method in exp3. The add method will also cause the StackOverflowError

https://i.stack.imgur.com/YPw5j.jpg

Any help/explanation would be appreciate. Thanks

Stopwatch class for the experiment

/**
 A class to measure time elapsed.
*/

public class Stopwatch
{
    private long startTime;
    private long stopTime;

    public static final double NANOS_PER_SEC = 1000000000.0;

    /**
     start the stop watch.
    */
    public void start(){
        startTime = System.nanoTime();
    }

    /**
     stop the stop watch.
    */
    public void stop()
    {   stopTime = System.nanoTime();   }

    /**
    elapsed time in seconds.
    @return the time recorded on the stopwatch in seconds
    */
    public double time()
    {   return (stopTime - startTime) / NANOS_PER_SEC;  }

    public String toString(){
        return "elapsed time: " + time() + " seconds.";
    }

    /**
    elapsed time in nanoseconds.
    @return the time recorded on the stopwatch in nanoseconds
    */
    public long timeInNanoseconds()
    {   return (stopTime - startTime);  }
}

OK. Thank everyone for the help. I'm really appreciate it. You guys answer so fast :)

Took me so long to see the connection here in the comments that I got a Stackoverflowerror. — Adam, Aug 07 '14 at 19:53
@atmin Not infinite, just deep. If it was infinite, it would error every time. — Patrick Collins, Aug 07 '14 at 19:55
@Patrick: you may be right here. Should read the questions before answering. — atmin, Aug 07 '14 at 19:59

score 3 · Answer 1 · edited Aug 07 '14 at 20:09

Your tree is not at all balanced and has degenerated to a linked list. Since you're adding in order, it will keep adding to the right side, and since there is no attempt to balance, the nodes will contain only right children.

To fix, look at some balancing algorithms or add in a different order to make it balanced. An unbalanced tree is inefficient and will slow your algorithms down as lookups and inserts will occur in O(n) instead of O(log n) time.

score 0 · Answer 2 · edited May 23 '17 at 11:43

The maximum depth of the stack in Java depends on how much memory you've allocated, it depends on the -Xss parameter.

Here, with your larger tests, your recursive function is getting deep enough to hit the limit. This post also mentions 32,000 as the magic number -- regardless, you can fix this by allocating more memory for the stack. You may need to allocate quite a lot if you want to be able to handle the worst case of 1,0240,000 layers.

The reason you're getting an error in the iterativeAdd case is because you're adding elements in reverse:

 if (n.getData().compareTo(data) > 0) {
            if (n.getLeft() == null) {
                n.setLeft(new BSTNode<E>(data));
                size++;
                return true;

instead of:

int diff = val.compareTo(n.getData());
        if (diff < 0)
            n.setLeft(addHelper(n.getLeft(), val));

Evidently, this is causing the tree to be built deeper, and so you get a StackOverflowError when you try to read it back.

score 0 · Answer 3 · answered Aug 07 '14 at 20:02

StackOverflowError simply means that your program exceeded the stack size. This error is the biggest danger of recursive calls, and from the posted stack trace we can see that in fact it's BinarySearchTree.heightHelper (both line 184 and 185 make a recursive call).

So we have left with three questions:

What is a stack? It's a data structure with an access pattern of LIFO (last element pushed to the stack is the first that will be pop'd)
What stack are we talking about? Each thread in the JVM is given a call stack, and this call stack has a fixed size decided at JVM boot time (you can adjust it to your needs)
Why the stack overflows? When you make a method call, the runtime must store local variables and return address somewhere. This somewhere is the thread stack. Every time a function is called, a new stack frame is created and pushed; when the function returns, the frame is popped from the stack. In the case of your failing experiment, you made too many calls to heightHelper: each recursive call push another stack frame, and you reach the point when there is no space available to make another call.

How do you solve it? You have two options:

Tune your JVM with the -ss parameter depending on the expected number of recursive calls
Change your implementation to use a loop - it may be more difficult to code, but the heap is order of magnitude bigger than the stack, so you won't run into stack overflows

Java - StackOverFlowError

3 Answers3