Find the element that will serve as the root element of a complete binary search tree. Give the index. I just need help finding the mathematical equation for this.

Printable View

- 11-29-2005Mr. AccludeFinding the Root of a Complete Tree
Find the element that will serve as the root element of a complete binary search tree. Give the index. I just need help finding the mathematical equation for this.

- 11-29-2005IfYouSaySo
Okay there are some things that are assumed here, for instance it is assumed that the data is in some particular format to begin with. Since your instructor asked for an index, I will guess that the data is in an array. So you need to figure out which element in the array will be the root element in the tree, and return the index. Now, ANY element could be the root, it really doesn't matter, so is the question really asking, "what is the ideal element for the root of the tree assuming 'ideal' means balanced?" And finally, you can ask yourself, if I want a balanced tree, what IS a good choice for a root element? Is it the smallest value? The largest? Does it matter? Why?

- 11-29-2005PJYelton
If I'm not mistaken, but doesn't a complete binary search tree have only one possibility for the root? I forget what the mathematical term for it is but I would think the root is always the number thats the middle of the of numbers, in other words the only number that has X items greater than it and X items less than it.

I don't think theres a mathematical equation for it though since the values could be heavily skewed for example the array [2,1,10000000] the root would be 2 but I don't know how you would come up with that with an equation. A simple algorithm could do it though. - 11-29-2005Rashakil FolQuote:

Originally Posted by**IfYouSaySo**

*does*matter. Given any ordering of elements, there is only one way to make a complete binary search tree.

Mr. Acclude, I believe your effort to figure out your calculation can be simplified with these questions, all directly calculable from the total number of elements.

1. How many elements will be in the bottom row of a tree of size N?

2. How many elements (in the bottom row) will lie to the left of the center of the tree?

3. How many elements*won't*be in the bottom row of the tree? Of these how many are left of center? - 11-29-2005IfYouSaySo
My mistake. 'Complete' basically means 'balanced'. It's probably a more strict definition actually. At any rate the choice is the middle element. I was going to let him figure that out, since it is homework and all, but whatever.

- 11-29-2005Mr. Acclude
No it's homework, teacher said to go think about it, and I was wondering and couldn't figure it out. And yea your right a algorithm not a equestion.