# BinarySearchTree - Having trouble adding elements to a vector from the tree. Recursive method! Help :)

• February 26th, 2013, 01:54 PM
prop
BinarySearchTree - Having trouble adding elements to a vector from the tree. Recursive method! Help :)
Hi, im trying to implement code for a binary search tree. This method should take all the elements in the tree and add them to a vector sorted with lowest first, the elements in the tree are inorder.

It gives me java.lang.ArrayIndexOutOfBoundsException at a[temp]=n.element;

Code java:

```/* * 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> n, E[] a, int index) {   return addArray(n, a, index);   }   private int addArray(BinaryNode<E> n, E[] a, int index){ if(n != null && index>=0 ){ int temp = index; temp = addArray(n.left, a, temp); a[temp]=n.element; temp++; temp = addArray(n.right, a, temp); return temp; } else { return index; }}```

Its a part of another public method that rebuilds the tree. The purpose of the rebuild method is to make the tree balanced.

Code java:

```/** * Builds a complete tree from the elements in the tree. */ public void rebuild() { E[] a = (E[]) new Comparable[size]; int first= 0; int last = toArray(root, a, first); root= buildTree(a, first, last-1 );   }```

And this is my main program where i test to add elements (ints) to the tree and then rebuild it:

Code java:

```public static void main(String[] args){   BSTVisualizer bstv = new BSTVisualizer("Fint träd", 500, 500); BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>(); // for(int i=3; i<10; i++){ // tree.add(i); // tree.add(i); // } tree.add(4); tree.add(5); tree.add(3); tree.add(1); tree.add(1); tree.add(2); tree.add(8); tree.add(7); tree.rebuild(); bstv.drawTree(tree);   System.out.println(tree.height()); System.out.println("//"); System.out.println(tree.size()); System.out.println("//"); tree.printTree();     } }```

I appreciate any help i receive! Ty!
• February 26th, 2013, 02:40 PM
Norm
Re: BinarySearchTree - Having trouble adding elements to a vector from the tree. Recursive method! Help :)
Quote:

its not working
Please explain what "not working" means. There are many ways for code to not work.

How can the code be compiled and executed for testing?

[code=java]
[/code]
to get highlighting and preserve formatting.
• February 26th, 2013, 05:22 PM
prop
Re: BinarySearchTree - Having trouble adding elements to a vector from the tree. Recursive method! Help :)
Quote:

Originally Posted by Norm
Please explain what "not working" means.

Sorry, ive edited the post now :)
• February 26th, 2013, 06:00 PM
Norm
Re: BinarySearchTree - Having trouble adding elements to a vector from the tree. Recursive method! Help :)
Quote:

java.lang.ArrayIndexOutOfBoundsException
Why is the index to the array past the end of the array?
Remember that the range of index for an array is 0 to the length-1.

The code should test for invalid indexes and not use them.
• February 27th, 2013, 12:24 PM
prop
Re: BinarySearchTree - Having trouble adding elements to a vector from the tree. Recursive method! Help :)
Well when i use the method i insert a empty vector with the length equal to the number of elements in the tree, u can see it under the method rebuild().
So it shouldnt be out of bounds.

I post the full binary search tree class here and maybe ull get a better picture of the problem.

Code java:

```package bst;   import java.util.NoSuchElementException;   import sun.org.mozilla.javascript.internal.Node;   public class BinarySearchTree<E extends Comparable<? super E>> { BinaryNode<E> root; int size;   /** * Constructs an empty binary searchtree. */ public BinarySearchTree() { root=null; }   /** * Inserts the specified element in the tree if no duplicate exists. * @param x element to be inserted * @return true if the the element was inserted */ public boolean add(E x) { if(root==null){ root = new BinaryNode<E>(x); return true; } else{ return add(root,x); }   }   private boolean add(BinaryNode<E> node, E x) { int comp = node.element.compareTo(x); if(comp==0){ return false; } else if(comp>0){ if(node.left==null){ node.left=new BinaryNode<E>(x); return true; } else { return add(node.left,x); } } else if(node.right==null){ node.right= new BinaryNode<E>(x); return true; } return add(node.right,x); }     /** * Computes the height of tree. * @return the height of the tree */ public int height() { return heightOfBinaryTree(root); }   /** * Returns the number of elements in this tree. * @return the number of elements in this tree */   public int size() { size=countsize(root); return size; }   private int countsize(BinaryNode<E> node) { if(node==null){ return 0; } if (node.left == null && node.right == null) { return 1; } else { return 1+countsize(node.left) + countsize(node.right); } }   /** * Print tree contents in order. */ public void printTree() { printNodes(root); }   private void printNodes(BinaryNode<E> node) { // if(node==null){ // throw new NoSuchElementException("Inget element"); // } else { if(node != null){ printNodes(node.left); System.out.println(node.element); printNodes(node.right); } }   /** * Builds a complete tree from the elements in the tree. */ public void rebuild() { E[] a = (E[]) new Comparable[size]; int first= 0; int last = toArray(root, a, first); root= buildTree(a, first, last-1 );   }   /* * 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> n, E[] a, int index) {   return addArray(n, a, index);   }   private int addArray(BinaryNode<E> n, E[] a, int index){ if(n != null && index>=0 ){ int temp = index; temp = addArray(n.left, a, temp); a[temp]=n.element; temp++; temp = addArray(n.right, a, temp); return temp; } else { return index; }}   /* * Builds a complete tree from the elements a[first]..a[last]. * Elements in the array a are assumed to be in ascending order. * Returns the root of tree. */ private BinaryNode<E> buildTree(E[] a, int first, int last) {   return constructTree(a, first, last); }   private BinaryNode<E> constructTree(E[] a, int first, int last) { int temp = (first+last)/2; if(first>last){ BinaryNode<E> node = new BinaryNode<E>(a[temp]); return node; } BinaryNode<E> nodeleft = constructTree(a, first, temp); BinaryNode<E> noderoot = new BinaryNode<E>(a[temp]); noderoot.left=nodeleft; BinaryNode<E> noderight = constructTree(a, temp, last); noderoot.right=noderight; return noderoot;   }   private int heightOfBinaryTree(BinaryNode<E> node) { if (node == null) { return 0; } else { return 1 + Math.max(heightOfBinaryTree(node.left), heightOfBinaryTree(node.right)); } }       static class BinaryNode<E> { E element; BinaryNode<E> left; BinaryNode<E> right;   private BinaryNode(E element) { this.element = element; } }   }```

And these are my full error messages, all linked to the same problem (using addArray method).

Code java:

```  Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0 at bst.BinarySearchTree.addArray(BinarySearchTree.java:125) at bst.BinarySearchTree.addArray(BinarySearchTree.java:124) at bst.BinarySearchTree.addArray(BinarySearchTree.java:124) at bst.BinarySearchTree.toArray(BinarySearchTree.java:117) at bst.BinarySearchTree.rebuild(BinarySearchTree.java:104) at bst.Main.main(Main.java:21)```