title: Find the best root for Binary Search Tree
body: <p>I am trying to find the best root for my binary search tree. i.e. this is my binary search tree.</p>
  
  <pre><code>         42
         /    \
        /      \
       25      53
      /  \    /  \
    23    41 49   55
   /  \  / \ / \ /  \
  </code></pre>
  
  <p>then I save them in an array in the form of inOrder walk.</p>
  
  <p>| 23 | 25 | 41 | 42 | 49 | 53 | 55 |.........<br>
  ...........&uarr;...........&uarr;...........&uarr;...........</p>
  
  <p>so the ones pointing the arrows are the nodes that I'll try to see which one is the best root 41, 42, 53.(the array can be bigger and I'll take the odd indexes of the array with a given Depth of the tree).</p>
  
  <p>So i have to try every single odd index as my new root and compare each height with the previous one and like that I can determine  which one is my best height. i.e. if I decided 25 is my new root I can have a tree like this</p>
  
  <pre><code>          25                            25
              \                             \
               \                             \
               42          or                 53
                 \                            /
                  53                         42
                    \                       /
  </code></pre>
  
  <p>so for each I check and compare the height with the previous node in the array and i return the node that it will give me the best node.
  So far i tried this:</p>
  
  <pre><code>void rebalance(){
  
      //this is the size for the array and NumDepth is defined at the constructor
  
      int size = (pow (2,(numDepth +1) )-1);
      Node* Array2 [size];
      int i = 0;
      int bestH = 0;
      Node* temp;
  
      for (int i=0; i &lt; size; i++){
              Array2[i]= new Node();
              Array2[i]= NULL;
      }
      //this function will be the one creates the inOrder walk and saves my nodes inside the array
      storeInOrder(rootBST, Array2, i, numDepth);
  
      temp = shortestBST(Array, rootBST, bestH, height);
  
  
  }
  
  Node* shortestBST(Node *root[], Node* root, int &amp;bestHeigth, int sizeA) {
  //root is my main tree basically 
  
  //this is how i know that i have to use the odd numbers in the array
  
      for(int i= 1; i&lt; sizeA; i+=2){
  
         //inside here I am supposed to do a recursion to check every node inside the array to check the node that is the best
        //they gave me a hint saying that i can point the nodes in the array to the ones in my main tree to create the tree with the new testing root in order to check if that node can create a best tree but i don't know how to do that using recursion
  //each of my nodes hold a key, a height and a size of a subtree , left to point to the left and a right to point to the right
  
      }
  
  
  
  
  }
  
  Node::Node() {
  
      sizeSub=0;
      height=1;
      key=0;
      left=NULL;
      right=NULL;
  }
  </code></pre>