Question

Okay so I am been wondering about this question for quite some time now, and want to know what will be the sample space?

WE have an empty BST, and we insert 1,2,3,4 in random order which is equally likely. What's the probability that the height of the resulting tree is 2?

Answer 1

have*

Answer 2

since the height has to be 2, I know that we can't insert in increasing or decreasing order since that would basically give a linked list of length 3 right

Answer 3

OOOOO. Interesting question. So, I think we have the following scenarios that are possible.

Hmm. So, I've been thinking about this for awhile and I'm realizing my knowledge of BST's has gotten rusty. I typed this whole thing out and then realized I was thinking AVL. Ok, I may need to come back to this in a bit. bahah.

Answer 4

So, there are what? 24 possible combinations in terms of how this could be inserted right?

Answer 5

The only case that I'm able to come up with offhand that yeilds a tree of length three is inserting the numbers in increasing or decreasing order. If 2 or 3 is the root, you yield a tree of length 2. So, you can get the answer here by approaching this by calculating the probability of the numbers being inserted in order, then subtract that from 1 to yield the probability of a tree of length 2.

Unless, of course, I'm a dum dum. Which is possible given my current level of sleep deprivation. ha.

Answer 6

so say
2
/ \
1 3
\
4
would be of height 2 right?

Answer 7

Yes, if my recollection is accurate the definition of height for a tree is the longest number of hops from the root to the farthest child. In this event, that is two.

Answer 8

right so even if we have the sample space to be 24, we would have to come up with 16 cases where height is 2 which is hard to get since probability that height = 2 is 2/3. I wonder if we would have 16 cases or not.

Answer 9

also the height of this tree would also be 2?
2
/ \
1 4
/
3

Answer 10

FML! I think I did get 16 such cases, why can't I think like this in the exam :(
16 cases for height = 2:
2, 1, 3, 4
2, 1, 4, 3
2, 3, 1, 4
2, 3, 4, 1
2, 4, 1, 3
2, 4, 3, 1
3, 1, 2, 4
3, 1, 4, 2
3, 2, 4, 1
3, 2, 1, 4
3, 4, 1, 2
3, 4, 2, 1
4, 2, 3, 1
4, 2, 1, 3
1, 3, 4, 2
1, 3, 2, 4

Answer 11

8 cases for height = 3:
4, 1, 2, 3
4, 1, 3, 2
4, 3, 1, 2
4, 3, 2, 1
1, 2, 3, 4
1, 2, 4, 3
1, 4, 3, 2
1, 4, 2, 3

0 cases for height = 1