Java - Balance a Binary Tree with "Brute Force"
<p>I'm trying to write a method in Java that balances a binary tree, described as follows:</p>

<blockquote>
  <p>... write an inorder traversal of the tree
  to an array and then use a recursive method (much like binary search) to insert the middle element of the array as the root, and then build balanced left and right subtrees.</p>
</blockquote>

<p>However, I'm stumped on how to do this all together. I've tried a variety of approaches so far, but nothing has worked. </p>

<p>I also already have an inOrder iterator that returns an ArrayList of all the elements in the tree, so that's covered.</p>

<p>This is what I'm currently building off of:</p>

<pre><code>public void rebalance()
{
    Iterator&lt;T&gt; it = iteratorInOrder();
    List&lt;T&gt; list = new ArrayList&lt;&gt;();

    while (it.hasNext())
    {
        list.add(it.next());
    }
    balanceRecursive( );
}

private void balanceRecursive( )
{
    //something here
}
</code></pre>

<p>and then I simply have this at the end of the add/remove element methods:</p>

<pre><code>if ((getHeight() - getMinHeight()) &gt; 5)
            rebalance();
</code></pre>

<p>So, how might I go about this? </p>