1

I am making an Binary Search Tree as an assignment.
I am having problem when i try to add 1,000,000 elements.
I'm getting error after 15,000 elements inserted:

Exception in thread "main" java.lang.StackOverflowError

Something wrong with my code i could not find where i did wrong.

public class BinarytreeInsert {

    public static void main(String[] args) {
        new BinarytreeInsert().run();
    }

    static class Node {

        Node left;
        Node right;
        int value;

        public Node(int value) {
            this.value = value;
        }
    }

    public void run() {
        Node rootnode = new Node(25);
        System.out.println("Building tree with root value " + rootnode.value);
        System.out.println("=================================");
        for(int i = 0 ; i<1_000_000;i++)
            insert(rootnode, i);

    }


    public void insert(Node node, int value) {
        if (value < node.value) {
            if (node.left != null) {
                insert(node.left, value);
            } else {
                System.out.println("  Inserted " + value + " to left of Node " + node.value);
                node.left = new Node(value);
            }
        } else if (value > node.value) {
            if (node.right != null) {
                insert(node.right, value);
            } else {
                System.out.println("  Inserted " + value + " to right of Node " + node.value);
                node.right = new Node(value);
            }
        }
    }
}
Ertuğrul Çetin
  • 5,131
  • 5
  • 37
  • 76
  • 6
    Your `insert` method is recursive. Any method call will put information about that instance of the method call on the "call stack" (and returning from a method removes it). This stack has limited memory space. If you call too many methods at once (usually during recursion), then that stack gets too big -- it overflows -- and the program terminates. – ajp15243 Jan 15 '14 at 14:22
  • 2
    And you should think about what your tree looks like when you repeatedly add elements in increasing order... – Gyro Gearless Jan 15 '14 at 14:24
  • 1
    You can look at http://stackoverflow.com/questions/8383976/how-to-add-elements-in-binary-search-tree-iteratively for how to implement an interative insertion algorithm. – Jason Jan 15 '14 at 14:25
  • 1
    The problem, as others have hinted, is that when you insert in increasing order, the binary tree becomes a linear list. So your recursion is 15,000 levels deep. Ideally, you need some way to balance your tree. Or you need an iterative insertion algorithm. – Jim Mischel Jan 15 '14 at 14:31

2 Answers2

5

As @ajp15243 mentions, the immediate cause of the problem is that you have a recursive insert method that is recursing too deeply. This fills the thread's method call stack, and triggers the exception.

The root problem is a design flaw in your algorithm, combined with "pathological" test data.

The problem is that your insert method does not attempt to create a balanced binary tree. That is, it does not attempt to create a tree where the left subtree of an node has (roughly) the same number of nodes as the right subtree.

The pathology is that the your algorithm combined with the test data results in a tree where the left child of every node is null. (Or something like that ...). The end result is that your tree is extremely unbalanced, and you have to recurse very deeply to find the insertion point.

There are a couple of ways to deal with this:

  • The ideal way would be to reimplement your tree using an algorithm that keeps the tree balanced, independent of the order in which elements are inserted.

  • The "cheat" way would be to figure out an insertion order that is going to result in a balanced tree ... with the current algorithm.

  • Finally, you could create an array of elements, shuffle the array and then insert the elements in shuffled order. That might result in a tree that is not perfectly balanced, but the chances of pathological behaviour will be vanishingly small.

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
  • 4th way to deal with it would be to change insert method to iterative. As long as runtime isn't a concern, this would get rid of the stack overflow problem. 5th way, and the real cheat way, is to increase the stack size. – gms7777 Jan 15 '14 at 16:14
  • @gms7777 - Noted. There are important caveats in both cases, however. – Stephen C Jan 15 '14 at 22:33
4

The problem is your insert function - since your tree is very deep, you recurse too deep. And Java, without compiler options, doesn't support particularly deep recursive calls.

The best solution would be to convert your recursive insert function to iterative. In short - just stick the code in your function in a loop, changing node at every iteration.

Additionally, I'd advise a self-balancing tree, such as a red-black tree.

Note that your tree will currently look something like this:

   25
  /  \ 
0     26
 \     \
  1     27
   \     \
    2     28
     \     ...
      3
       ...

This will be much deeper than it needs to be (indeed it will be O(n) height, which will, in turn, lead to O(n) operations on the tree).

With a self-balancing tree, the height will never be more than O(log n).

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
  • 1
    Suggested reading if you don't know what `O(...)` means - [Plain English explanation of Big O](http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o). – Bernhard Barker Jan 15 '14 at 14:36
  • 1
    In fact, the height is not just `O(log N)`. It should be very close to `log N` ... without a scaling constant. (Saying that a number is "close to `O(...)`" is mathematical nonsense, because `O(...)` is a shorthand notation for a limit, not a number.) – Stephen C Jan 15 '14 at 14:43