title: Binary Search Tree in Java using arrays
body: <p>I'm trying to write an array implementation of Binary Search Trees in Java. To that end, I have the following two methods that are responsible for making sure all the data gets added into the array properly</p>
  
  <pre><code>private int[] testData = {50, 25, 75, 10, 15, 5, 53, 29, 79, 78, 111, 33};
  private int[] tree = new int[100];
  private final int ROOT = tree.length / 2; //Root is at the center of the array
  
  public void insert(int key)
  {
      if(tree[ROOT] == 0)
      {
          tree[ROOT] = key;
      }
      else
      {
          int locToInsert = findLocationToInsert(ROOT, key);
          if(locToInsert == -1)
          {
              System.out.println("Error: Tree branch full");
          }
          else
          {
              tree[locToInsert] = key;
          }
      }
  }
  
  public int findLocationToInsert(int c, int key)
  {
      if(tree[c] != 0) //If current c is not empty
      {
          if(key &gt; tree[c]) //Go right to find an empty c
          {
              findLocationToInsert(c + c/2, key);
          }
          else //Go left to find an empty c
          {
              findLocationToInsert(c - c/2, key);
          }
      }
      return c;
  }
  </code></pre>
  
  <p>However, my recursive findLocationToInsert method always returns the root. How do I fix this implementation to return the first empty location it finds?</p>