Java StackOverflowError while recursively building an array from a binary search tree.

Question

I'm trying to balance a BST by first building an array (inorder) and then rebuild the entire tree from my array.

I have:

 public void toArray(E[] a) {
  toArray(root, a, 0);
 }

 /*
  * Adds all elements from the tree rooted at n in inorder to the array a
  * starting at a[index].
  * Returns the index of the last inserted element + 1 (the first empty
  * position in a).
  */
 private int toArray(BinaryNode<E> node, E[] a, int index) {
  if (node.left != null) {
   index = toArray(node, a, index);
  }

  a[index] = node.element;
  index++;

  if (node.right != null) {
   index = toArray(node, a, index);
  }

  return index;
 }

and:

bst.toArray(b);

I was hoping that this would build an array inorder. But i get StackOverflowError. As I understand that is probably due to infinite recursion but I really can't see it.

The error occurs on this line:

index = toArray(node, a, index);

Any help appreciated.

Answer 1

here it is:

if (node.left != null) {
    index = toArray(node, a, index);
}

you've probably wanted to do something with index (increment for example) or with the node (like, node = node.left) (I didn't investigate your algorithm, just general suggestions).

Answer 2

index = toArray(node, a, index);

You wanted to write node.left or node.right?