How can I fix my array so I don't have an IndexOutOfBoundsException?

Question

For a HW assignment, I was tasked to add a bunch of methods into a BinarySearchTree class. Two methods I have are balance and InsertTree (I think it should've been named InsertNode). The authors from the textbook provided pseudo code of what the methods should look like. Both methods work with each other; balance is supposed to take an unbalanced tree and insert each element into an array. I believe InsertTree is supposed to take the elements from the array and put them back into the new formed tree.

The BST Class itself is quite large so I don't think posting it is a good idea. But you can find the Source code here under Sample Materials. The code in reference is in the ch07.trees package.

This is my interpretation of the authors pseudo code so far:

ArrayList<T> array = new ArrayList<T>();

public void balance()
// Will read, store, and recreate the tree
{
      Iterator<T> iter = this.iterator();
      int index = 0;
      while(iter.hasNext())
      {
          array.add(iter.next());
                  index++;
      }
      System.out.println(array.toString());
      System.out.println(index);

      tree = new BinarySearchTree<T>();
      tree.InsertTree(0, index -1);
  }

public void InsertTree(int low, int high)
// Will find the mid-point and insert other elements into left and right subtrees
  {
      if (low == high)
      {
          tree.add(array.get(low));
      }
      else if((low + 1) == high)
      {
          tree.add(array.get(low));
          tree.add(array.get(high));
      }
      else
      {
            int mid = (low + high)/2; 
            tree.add(array.get(mid));
            tree.InsertTree(low,mid-1);
            tree.InsertTree(mid+1,high);
      }
  }

I have to use ArrayList because all of the methods are generics of type T. In my driver class I am simply adding an unbalanced set of elements [A, B, C, D, E, F] and index will correctly show I have incremented index to 6. But, when the new tree calls for InsertTree( 0, index - 1), I get this:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 2, Size: 0
at java.util.ArrayList.rangeCheck(Unknown Source)
at java.util.ArrayList.get(Unknown Source)
at ch07.trees.BinarySearchTree.InsertTree(BinarySearchTree.java:180)
at ch07.trees.BinarySearchTree.balance(BinarySearchTree.java:163)
at ch07.trees.HWDriver.main(HWDriver.java:67)

Line 163 is tree.InsertTree(0, index -1); and Line 180 is tree.add(array.get(mid));

Seems the problem is involved with the mid-point, but I'm not sure what the issue could be. I'm not an expert at using ArrayLists, so any help on solving this would be much appreciated.

edit:

I believe the problem has been fixed. I put the array that I created back into the balance method instead of outside the method, and added the array to the InsertTree methods arguments. Then, I had to change every conditional output from this.tree.add to this.add. I also moved my BinarySearchTree tree back into the balanced method because before I was getting a NullPointerException.

Whether or not my method is working as intended is still to be determined.

Answer 1

Here is your answer more concisely:

this.tree = new BinarySearchTree<T>();
this.tree.InsertTree(0, index-1);

So you have created a new, empty tree and stored it in the member variable "tree". You then attempt tell your new, empty tree to insertTree(0, 5) .