0
$\begingroup$

I need to calculate the expected height of a randomly built binary search tree, BST, with 4 different keys: $x < y < z < w$

According to Catalan numbers, there are 14 possible trees, 8 with height 3 and 6 with height 2. So let $X$ be a random discrete variable that holds the tree height, $P\{X=2\}=\frac{6}{14}=\frac{3}{7}$ and $P\{X=3\}=\frac{8}{14}=\frac{4}{7}$ hence $E[X]=2\cdot \frac{3}{7} + 3\cdot\frac{4}{7} = \frac{18}{7}\approx 2.571$

But then I thought, not all the trees in Catalan numbers has the same probability of occurring as there are 24 ways to order the keys, so instead I get $P\{X=2\}=\frac{16}{24}=\frac{2}{3}$ and $P\{X=3\}=\frac{8}{24}=\frac{1}{3}$ and $E[X]=2\cdot \frac{2}{3} + 3\cdot\frac{1}{3} = \frac{4}{3} + 1 = \frac{7}{3} \approx 2.333$

I'm not sure which way is the correct way to calculate the probability of the possible values for $X$

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ To meaningfully talk about the expected height you need to define a distribution, i.e. how do you generate your random BST? $\endgroup$
    – Tassle
    Commented Jun 9, 2021 at 20:50
  • $\begingroup$ There are $4!$ possible permutation so each permutation has a probability of $\frac{1}{24}$, thus I have 24 possible trees but only 14 are unique $\endgroup$
    – CforLinux
    Commented Jun 9, 2021 at 20:58
  • 2
    $\begingroup$ That doesn't really answer my question. Do you want a uniform distribution over all unique trees? Or are you generating BSTs based on a certain procedure applied to a sequence of keys and want the uniform distribution over all permutations of keys? Something else? There cannot be a right answer before who have totally specified what you want to compute. $\endgroup$
    – Tassle
    Commented Jun 9, 2021 at 21:11
  • $\begingroup$ I don't really know, it wasn't specified, I was only told the order in which the elements are inserted to the tree is random and I need calculate the expected height. Originally I thought the randomness is in choosing a unique tree "shape", but now I think it was referring to the possible permutations which I assume have a uniform distribution as nothing else was specified $\endgroup$
    – CforLinux
    Commented Jun 9, 2021 at 21:26
  • 1
    $\begingroup$ Where did you encounter this task? Please credit the original source. If you don't know, you'll need to go ask the source to figure that out. The question isn't answerable without more information. $\endgroup$
    – D.W. ♦
    Commented Jun 9, 2021 at 22:09

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.