Copying a sorted array to a balanced inorder Binary Search Tree

[RingmasterTJ]

Hey everyone,

So, for my C++ course I am implementing a Binary Search Tree. In this Binary Search Tree we are to create a function to copy the values of a passed array into a Balanced Binary Search Tree that will render a correct inorder traversal.

I.E. an array of 0, 1, 2 will be in the tree in Root->1, Left->0, Right->2

I think I'm pretty close to figuring out the function (which is good considering how long I've been working on it;) ). However, I'm having issues on figuring out not only my base case, but also if passing mid in is the correct way to go about "altering" my values.

I know line 25 is wrong, as well as (I think) line 20 but I'm not sure where to go from here...Any help would be greatly appreciated!

PS: The while loop in the first function is to find out what the highest subscript with a stored value in the array is. We are guaranteed to be passed a statically allocated array of 99 elements, but we have to find out how many elements are in the array. Thus the loop.

//------------------------------ arrayToBSTree --------------------------------
void BSTree::arrayToBSTree(NodeData *data[]) {
	this->makeEmpty();
	int i = 0;
	int high = i;
	while(data[i] != NULL && i <= 99) {
		high = i;
		i++;
	}
	this->overallRoot = toTreeHelper(data, 0, high, this->overallRoot);
}

//------------------------------ toTreeHelper ---------------------------------
BSTree::Node* BSTree::toTreeHelper(NodeData *data[], int low, int high, 
								   Node *root) {
	int mid = (low + high) / 2;
	root = new Node;
	root->left = root->right = NULL;
	root->data = NULL;
	if(mid != 0) {
		root->left = toTreeHelper(data, low, mid, root->left);
	}
	root->data = data[mid];
	data[mid] = NULL;
	if(mid != 0 || mid != high - 1) {
		root->right = toTreeHelper(data, mid + 1, high, root->right);
	}
	return root;
}

[Murtan]

I'd like to experiment with the code to try it, but in the interest of a quick answer, try low < mid on line 20 and mid < high on line 25.

Basic translation: If there are values between low and high that are lower than mid, add them to the left. If there are values between low and high that are higher than mid, add them to the right.

[Rashakil Fol]

It makes no sense to check if mid != 0. How could mid be 0? Well, in most cases, mid could not be 0, except at the very left edge of the tree. So your checks for the base case are bad.

Basically your hard job is to consider the cases where high - low is 0 (if possible), 1 (if possible), 2, 3, maybe 4, and in general, even or odd.

Also, you should look twice at your arrayToBSTree function: you might go past the end of the array.

Basically, this problem is designed to get you to practice thinking about off-by-one errors.

[RingmasterTJ]

Appreciate the help Murtan, but unfortunately, that doesn't quite give the optimal balance for the tree. Another big sticking point with me...

[Murtan]

Ok, so what kind of tree does it build?

How is it sub-optimal?

What would you have to change to make it optimal?

[Rashakil Fol]

If you want optimal balance, you'll need to think carefully about the case where the size of the segment you're working on is a power of two. You need to split that cleanly in half. Are you splitting it cleanly in half?

Also, what do you think the value of root->left is in:

root->left = toTreeHelper(data, low, mid, root->left);

[Murtan]

Ok, so I have the values 0,1,2,3,4,5,6,7,8,9,10 in those positions in the input array...

You caclulate mid as (low + high) /2 so the first mid is 5?

we put 5 at the root and iterate left with (0,4) and right with (6,10)

(0,4): mid=2 we put 2 to the left of 5 [left: (0,1) right: (3,4)]
(0,1): mid=0 we put 0 to the left of 2 [left: none right: (1,1)]
(1,1): mid=1 we put 1 to the right of 0 [none]
(3,4): mid=3 we put 3 to the right of 2 [left:none right: (4,4)]
(4,4): mid=4 we put 4 to the right of 3

(6,10): mid=8 we put 8 to the right of 5 [left: (6,7) right: (9,10)]
(6,7): mid=6 we put 6 to the left of 8 [left: none right: (7,7)]
(7,7): mid=7 we put 7 to the right of 6
(9,10): mid=9 we put 9 to the right of 8 [left:none right: (10,10)]
(10,10): mid=10 we put 10 to the right of 9 [none]

so we built something like:

5
    2      8
 0   3   6   9
z 1 z 4 z 7 z 10

The z's are empty nodes. How much more balanced does that need to be?

[RingmasterTJ]

Wow, you both are amazing. Thank you so much. You guys not only helped me to get the program to work, but made me find bugs I did not even realize I had.

Again, thank you, I really appreciate both of you taking time out of your day to help me get this ironed out!:icon_smile:

[monster8]

what was changed to get it to work?

[RingmasterTJ]

The values I was passing in were off, that was the big issue. & as Murtan stated, the checks should have been changed.

[monster8]

i see, my approach was a little different because I did not return a node, but i eventually got it to work. I think you are in my class with Zander?

[wieczorek1990]

I did something similar but easier to understand

void binary_half(int low, int high)
{
    int mid = (low + high) / 2;
    root = insert_bst(id_table[mid], root); //recursive - id, root address
    if (mid != low)
        binary_half(low, mid);
    if (mid != high)
        binary_half(mid+1, high);
}