# Calculating the expected height of a randomly built binary search tree

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]=2cdot frac{3}{7} + 3cdotfrac{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]=2cdot frac{2}{3} + 3cdotfrac{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$$