title: Balancing a Binary Search Tree (BST)
body: <p>I'm trying to make a balance_bst(bstNode root) function, but i'm struggling with the implementation.</p>
  
  <p>I'm implementing the function as a template function, since my bstNode class is a template class.</p>
  
  <p>Here is (some of) my code:</p>
  
  <pre><code>template&lt;class Item, class  Key&gt;
  class bstNode{
  public:
      //Constructor
      bstNode(const Item&amp; init_data = Item(), const Key&amp; init_key = Key(), bstNode&lt;Item, Key&gt;* l_child = NULL, bstNode&lt;Item, Key&gt;* r_child = NULL){
          data_field = init_data;
          key_field = init_key;
          l_ptr = l_child;
          r_ptr = r_child;
      }
      //Destructor
      ~bstNode(){
          data_field = 0;
          key_field = 0;
          l_ptr = r_ptr = NULL;
      }
      //Basic Member Functions
      bstNode&lt;Item, Key&gt;*&amp; left( )   {                    return l_ptr;       }           //returns left child pointer by reference
      bstNode&lt;Item, Key&gt;*&amp; right( )  {                    return r_ptr;       }           //returns right child pointer by reference
      bstNode&lt;Item, Key&gt;* left( ) const   {               return l_ptr;       }       //returns left child pointer by reference
      bstNode&lt;Item, Key&gt;* right( ) const  {               return r_ptr;       }       //returns right child pointer by reference
      const Item&amp; data() const{                           return data_field;  }           //returns reference to data_field
      const Key&amp; key()const {                             return key_field;   }
      Item&amp; data() {                                      return data_field;  }           //returns reference to data_field
      Key&amp; key() {                                        return key_field;   }
      void set_data(const Item&amp; new_data){            data_field = new_data;      }       //sets data_field to new_data
      void set_key(const Key&amp; new_key){               key_field = new_key;        }       //sets key_field to new_key
      void set_left(bstNode* new_left){               l_ptr = new_left;           }       //sets left child pointer to new_left
      void set_right(bstNode* new_right){             r_ptr = new_right;          }       //sets right child pointer to new_right
  
  private:
      bstNode&lt;Item, Key&gt;  *l_ptr,     //pointer to left child node 
                          *r_ptr;     //pointer to right child node
      Item    data_field;
      Key     key_field;
  };
  
  template&lt;class Item, class Key&gt;
  void balance_bst(bstNode&lt;Item, Key&gt;*&amp; root){                //unfinished
  
      std::vector&lt; bstNode&lt;Item, Key&gt;* &gt; nodes;
      sorter(root, nodes);
      size_t i = nodes.size()/2;                      //size() divided by 2 will yield
                                                      //index of middle element of vector for 
                                                      //odd-isized arrays and the greater of the 
                                                      //middle two elements for an even-sized array
  
      while(i&gt;=0){
          root-&gt;set_key(nodes[i]-&gt;key());                             
          root-&gt;set_data(nodes[i]-&gt;data());
           //.....MORE CODE HERE: recursive call??
  
      }
  
  
  }
  
  template&lt;class Item, class Key&gt;
  void sorter(bstNode&lt;Item, Key&gt;*&amp; root, std::vector&lt;bstNode&lt;Item, Key&gt;* &gt;&amp; tree_nodes){
      if(root == NULL)
          return;
      sorter(root-&gt;left(), tree_nodes);
      tree_nodes.push_back(root);
      sorter(root-&gt;right(), tree_nodes); 
  }
  </code></pre>
  
  <p>I've been messing with the actual balance_bst function, and think that recursion is the obvious solution but i can't seem to wrap my head around this one...</p>
  
  <p>sorter basically inserts the elements of a BST into a vector using an inorder processing algorithm.  So as long as "root" is a pointer to the root of a binary search tree(ie all key values of a nodes left subtree are less than the key value of the nodes and all key values of the nodes right subtree are greater than the nodes) then the nodes inserted into the vector will be sorter in an ascending manner.</p>
  
  <p>Then, to create a balanced tree, i insert the node at the center of the vector at the root of the tree, and then should be able to recursively insert the left and right children nodes which would then be at the middle of the left half of the vector and the middle of the right half of the vector.</p>
  
  <p>Note: i understand that this is using integer division and that say, 7/2 = 3, which would be the index of the middle element of an array of size 7.  And for even-sized arrays, the algorithm implemented above will find the index of the greater of the two elements in the middle of the vector.</p>
  
  <p>Anyway, any suggestions or observations are welcomed and encouraged!  Thanks in advance. </p>
  
  <p>Edit:  What I am asking is how do I implement a function to balance a binary search tree?
  (A balanced BST is one that has the minimum depth it can given the number of nodes.)</p>