CODEWITHSUNDEEP
javarecursionbinary-tree
leigero
leigero

Reputation: 3283

Recursively call a method to build Binary Search Tree

I'm trying to build a binary search tree given an ArrayList of sorted values. In trying to create the most efficient tree possible I take the middle value, and add it to the tree. Then recursively take the leftmost values and find the middle of those values entering THAT into the tree.

Once done the same is done with the right side.

I call the balanceBST() method with the following line:

balanceBST(iterator.list, 0, iterator.list.size() - 1);

given that iterator.list is an ArrayList of integers at the moment containing values:
{5, 17, 24, 31, 44, 55, 71, 81, 82, 83, 84, 85, 97}

public void balanceBST(ArrayList<E> values, int start, int end){
  int mid = (start + end) / 2;
  while(mid >= 0 && end > mid){ 
      insert(values.get(mid));
      balanceBST(values, start, mid - 1);
      balanceBST(values, mid + 1, end);
    }
}

the insert(element) method does the leg work of entering things into the binary tree.

This is yielding all kinds of errors and I presume it happens when mid approaches 0 or when the end approaches mid it messes up but I followed the logic myself and I'm not understanding why this is crashing.

EDIT:

For those reading this in the future big thanks to @David. The following fixed the problem:

  public void balanceBST(ArrayList<E> values, int start, int end){
  int mid = (start + end) / 2;
  if(end < 0 || start > end) return;
      insert(values.get(mid));
      balanceBST(values, start, mid - 1);
      balanceBST(values, mid + 1, end);
  }

Upvotes: 1

Views: 1908

Answers (1)

David Elliman
David Elliman

Reputation: 1399

As you are doing a recursive call to balanceBST you do not want the while loop which will result in entries being repeatedly inserted. Change the while to a termination test and return. Take care to only insert >= 0 and < end and exit when both are false.

Upvotes: 2

Related Questions