Find the best root for Binary Search Tree

Question

I am trying to find the best root for my binary search tree. i.e. this is my binary search tree.

         42
       /    \
      /      \
     25      53
    /  \    /  \
  23    41 49   55
 /  \  / \ / \ /  \

then I save them in an array in the form of inOrder walk.

| 23 | 25 | 41 | 42 | 49 | 53 | 55 |.........
...........↑...........↑...........↑...........

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).

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

          25                            25
            \                             \
             \                             \
             42          or                 53
               \                            /
                53                         42
                  \                       /

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:

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 < 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 &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< 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;
}

I’m confused about why you “have to” try each odd index as a root. Is there some requirement that says you need to do this? Why aren’t you considering even roots? — templatetypedef, Oct 31 '17 at 15:50
yeah its a requirement to try only the odd index, they call it singletons. i can explain more if you want me to. — Bryan, Oct 31 '17 at 15:58
@Bryan `int size = (pow (2,(numDepth +1) )-1); Node* Array2 [size];` -- There are at least two things wrong or just dangerous in those two lines of code. First `pow` when used with integer exponents is not guaranteed to give you the correct results. [See this](https://stackoverflow.com/questions/25678481/why-does-pown-2-return-24-when-n-5-with-my-compiler-and-os/25678721#25678721). Second `Node* Array2[size]` is not legal C++ syntax, as arrays must be declared using a constant to denote the number of entries. — PaulMcKenzie, Oct 31 '17 at 16:00
Yes, can you please explain more? I’m having a lot of trouble seeing what it is that you’re trying to do here. — templatetypedef, Oct 31 '17 at 16:14

score 1 · Answer 1 · answered Oct 31 '17 at 15:38

1

Since you're starting with the numbers in sorted order, finding the root node is pretty trivial: the ideal root is the median of the numbers to be inserted.

This makes it fairly trivial to do the insertion recursively: find the median, insert it as the root, then insert the left sub-array as the left child and the right sub-array as the right child.

answered Oct 31 '17 at 15:38

Jerry Coffin

476,176
80
629
1,111

yeah i did it like that at the beginning but they want it to check for every odd index in the array as a new root. Thats why I'm getting problems trying to find the new best root – Bryan Oct 31 '17 at 15:41
Why would you check every odd index, when you know that any other than the median is going to give an imbalanced tree? – Jerry Coffin Oct 31 '17 at 16:00
As I reckon, root may be optional, but the task here is to build a well balanced tree, having height parameter in every node leads to AVL-Tree balancing algorithm, which is well documented in the internet. – Victor Oct 31 '17 at 16:05
If I'm right you need to compare heights, and if they differ do operations called "tree rotations" – Victor Oct 31 '17 at 16:09
1

@Victor: That's completely unnecessary under the circumstances. AVL (and Red-Black) let you *maintain* a (reasonably) balanced tree in the face of random insertions and deletions. OP doesn't mention anything about random insertions and deletions. – Jerry Coffin Oct 31 '17 at 16:13
@jerry disagree, AVL gives as close to perfect balanced tree as is practical, and the fact that it can be used to maintain balance doesn't make it any worse for building balanced tree in the first place. There's a sizeSub node attribute, that's a strong reference and a drawback of AVL is the need to store that number, and it seems like that's what is expected here. There's no reference for Red And Black method, so no need discussing or mentioning here. – Victor Oct 31 '17 at 16:34
@Victor: Sorry, but you're simply wrong. An AVL tree is worse in at least three respects. First, it builds a tree that can be deeper than ideal (where which the method I've suggested avoids). Second, what I've suggested does each insertion with O(1) complexity, but an AVL tree uses O(log N) complexity for each insertion. Third, an AVL tree requires storing extra data that's completely unnecessary for the case at hand. – Jerry Coffin Nov 01 '17 at 03:18

score 0 · Accepted Answer · answered Oct 31 '17 at 16:45

There's a similar question and an algorithm that looks like just what is being asked of here:

Using right-rotation operations, turn the tree into a linked list (a.k.a. backbone or vine)
Rotate every second node of the backbone about its parent to turn the backbone into a perfectly balanced BST.

http://www.geekviewpoint.com/java/bst/dsw_algorithm

Find the best root for Binary Search Tree

2 Answers2