title: Balancing a binary search tree
body: <p>Ok, I am trying to get a binary search tree to balance, and I know why it's not working, but I don't know how to fix it. This is what I have for my balancing methods.</p>
  
  <pre><code>    public void balance(){
      if(isEmpty()){
          System.out.println("Empty Tree");
          return;
      }
      if(!isEmpty()){
          values = new Object[count()];
          index = 0;
          createAscendingArray(root);
          clear();
          balanceRecursive(0, index);
                      values = null;
      }
  
  
  }
  
  private void createAscendingArray(TreeNode&lt;E&gt; current){
      if(current == null)
          return;
      if(current.getLeftNode() != null)
          createAscendingArray(current.getLeftNode());
      else if(current.getRightNode() != null)
          createAscendingArray(current.getRightNode());
      values[index] = current.getData();
      index++;
  
  
  }
  
  private void balanceRecursive(int low, int high){
      if(low == high)
          return;
      else if(low &gt; high/2)
          balanceRecursive(high/2, high);
      else if(low &lt; high/2)
          balanceRecursive(low, high/2);  
  
      E insert = (E) values[(low + high)/2];
      insertItem(insert);
  
  }
  </code></pre>
  
  <p>To add some clarity, index is a predefined private int variable, values is also a predefined Object[]. Root is the node at the start of my unbalanced tree. First off, I know my array is adding the values in reverse order. Right now I'm just testing with 1, 2, 3, 4, 5, 6 being added to the tree, so then my array comes out with 654321. I'm not sure how I need to place the addition of the values to my array so that it will add them in the correct ascending instead of descending order.</p>
  
  <p>Now when I look at my code, I know that the balanceRecursive() method is never going to work for implementing the top half of the array. My issue is I don't know how to write it so that it will. I am tasked to do this with recursion, which I am not very familiar with. I could do this with iteration, but it's strictly defined I must use recursion.</p>
  
  <p>Balance is supposed to work like this:
  Algorithm for balance() </p>
  
  <ul>
  <li>Check if tree is empty </li>
  </ul>
  
  <p>o If it is, print “Empty Tree” </p>
  
  <p>o Return </p>
  
  <ul>
  <li>If tree is not Empty </li>
  </ul>
  
  <p>o Create array of Objects the size of the Tree </p>
  
  <p>o Set index to 0 </p>
  
  <p>o Populate the array with all values in ASCENDING order (createAscendingArray()) </p>
  
  <p>o Clear Tree </p>
  
  <p>o Repopulate Tree from Object array (balanceRecursive()) </p>
  
  <p>o Set the values array to null</p>
  
  <p>(I have methods written already for count() to count the number of nodes in my tree and clear() to empty the tree)</p>
  
  <p>balanceRecursive() is supposed to do the following
  Repopulates the Tree with the values in the values data member. These must be added in the appropriate order to create a balanced tree. </p>
  
  <ul>
  <li><p>Add the middle element </p></li>
  <li><p>This creates two sub arrays, a left and a right </p></li>
  <li><p>Add the middle of those sub arrays </p></li>
  <li><p>This creates even more sub arrays</p></li>
  <li><p>Keep adding middles of sub arrays until there are none </p></li>
  </ul>
  
  <p>I know for this method I am never using the larger set of sub arrays and that's the part of the recursion that I can't figure out how to implement. Any suggestions on how to clean up my recursion?</p>
  
  <p>EDIT:</p>
  
  <p>I changed my createAscendingArray() to the following:</p>
  
  <pre><code>    private void createAscendingArray(TreeNode&lt;E&gt; current){
  
      if(current == null)
          return;
      createAscendingArray(current.getLeftNode());
      values[index] = current.getData();
      index++;
      createAscendingArray(current.getRightNode());
  
  
  
  }
  </code></pre>
  
  <p>That should function like an inOrder traverse of the BST am I right?</p>