Exception in thread "main" java.lang.StackOverflowError

Question

Error received:

Exception in thread "main" java.lang.StackOverflowError
    at AVL.insert(AVL.java:45)

I am not familiar with the error I was given, but I do know that it only happens when the array being used to build the AVL tree is a vary large size and is occurring during insert when moving to the right side of the tree. I am not sure why this is happening though (in other words I do not know exactly what StackOverflowError is and why it is happening).

AVL class:

//AVL.java
import java.util.*;
import java.io.*;

public class AVL{
    AvlNode root;

   public void tree(int[] list){
      for(int i=0; i<list.length; i++){
         insertPrep(list[i]);
      }
   }

   public void insertPrep(int data){
      if (root==null){root = new AvlNode(data);}
        else {
         AvlNode newNode = new AvlNode(data);
         root = insert(root, newNode);
         root = rebalance(root);
         adjustHeight(root);
      }
    }

   public AvlNode insert(AvlNode node, AvlNode newNode){
      if (node.key > newNode.key){
         if(node.left!=null){node.left=insert(node.left , newNode);}
         else{node.left=newNode;}
      }
      else if (node.key < newNode.key){
         if(node.right!=null){node.right=insert(node.right, newNode);}
         else{node.right=newNode;}
      }
      AvlNode result = rebalance(node); 
      adjustHeight(result);
      return result;
   }

   public int height (AvlNode node ){
      if (node == null){return 0;}
      else {return node.height;}
   }

   public void adjustHeight (AvlNode node){
      if (root != null){ root.height = 1+ Math.max(height(root.left),height(root.right));}
   }

   public AvlNode rebalance (AvlNode node){
      AvlNode newAvlNode = node;

      if (node.left != null && node.right != null){
        if (node.left.height-node.right.height==2){
            if (node.left.left.height>node.left.right.height){
                AvlNode n2 = node.left;
                AvlNode n3 = node;
                n3.left = n2.right;
                n2.right = n3;

                adjustHeight(n3);
                adjustHeight(n2);
                newAvlNode = n2;
            } else {
                AvlNode n1 = node.left;
                AvlNode n2 = node.left.right;
                AvlNode n3 = node;
                n1.right = n2.left;
                n2.left = n1;
                n3.left = n2.right;
                n2.right = n3;

                adjustHeight(n1);
                adjustHeight(n3);
                adjustHeight(n2);
                newAvlNode = n2;
            }
        } else if (node.right.height-node.left.height==2){
            if (node.right.right.height>node.right.left.height){
                AvlNode n1 = node;
                AvlNode n2 = node.right;
                n1.right = n2.left;
                n2.left = n1;

                adjustHeight(n1);
                adjustHeight(n2);
                newAvlNode = n2;
            } else {
                AvlNode n1 = node;
                AvlNode n2 = node.right.left;
                AvlNode n3 = node.right;
                n1.right = n2.left;
                n2.left = n1;
                n3.left = n2.right;
                n2.right = n3;

                adjustHeight(n1);
                adjustHeight(n3);
                adjustHeight(n2);
                newAvlNode = n2;
            }
        }
      }
    return newAvlNode;
   }

   class AvlNode{
    int key, height; //data for input numbers and height for height of nodes to keep balance
    AvlNode left, right; //left for left side of tree and right for right side of tree

      AvlNode(int data){
         key = data;
      }

   }
}

Class using AVL:

//Tree.java
import java.io.*;
import java.util.*;

public class Tree{

   public static void main(String[] args){

      int n = 30000; //numbers to be in arrays
      int a[] = new int[n]; //first array

      for (int i=0; i<n; i++){
         a[i] = i+1; //insert #'s 1-n; smallest to largest
      }

      //send arrays to be put in AVL trees
      AVL avl = new AVL();
      double timeSoFar = (double)System.nanoTime();
      avl.tree(a);
      double treeTime = (double)System.nanoTime() - timeSoFar;
      printTime('a',treeTime, "AVL");

   }

   public static void printTime(char l, double treeTime, String tree){
      double treeTimeMin = treeTime/600000;
      treeTimeMin/=100000;
      System.out.println("Elapsed time for building " + tree + " " + "Tree for array '" + l + "': " + treeTime + " nanoseconds, or: " + treeTimeMin + " minutes.");
   }

}

Answer 1

Since your array is sorted from smallest to largest, when you try to insert the, say, 15000th node using insertPrep (see the loop in tree()), you are going to recursively call insert(AvlNode node, AvlNode newNode) 15000 times.

This is due to the test in insert

  if (node.key > newNode.key){
     if(node.left!=null){node.left=insert(node.left , newNode);}
     else{node.left=newNode;}
  }

The recursions are too deep

Recursion is probably not your best choice to find the location in the tree and you should resort to a loop which will be more efficient anyway because you do not have to accumulate the frames between the calls.

Alternatively, use a language such as Scala that knows about tail recursion and automatically unfolds tail recursions to loops at compile time.

EDIT The explanation for the Overflow is probably over simplistic. See comments below

Answer 2

I think there is something wrong with re-balancing.

You are doing

AvlNode result = rebalance(node); 
adjustHeight(result);

which looks weird to me because you should adjust the height first then re-balance then adjust height again. Looks like re-balancing never happened because height is never updated; hence, your tree will be very high; hence, the stack overflow exception.

I am not 100% certain, but that looks like the problem. One sanity check you can do is to create, say, 100 nodes and check if your tree is balanced. If not, you didn't implement the balancing properly.