Calculating the expected height of a randomly built binary search tree

Question

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$

• Tassle: To meaningfully talk about the expected height you need to define a distribution, i.e. how do you generate your random BST?
• CforLinux: 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
• Tassle: 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.
• CforLinux: 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
• D.W.: 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.