# Randomly generated binary search trees case comparison

Although not an assignment, just out of curiosity; I am trying to compare a two cases

1. A scenario where I pick a tree out of the set of possible binary search trees on the keys $$1,2,\ldots,n$$, with each tree equally likely (with a probability say, $$p(T)$$) and\
2. Generating a binary search tree by inserting the numbers $$1,2,\ldots,n$$ in random order with a probability, $$q(T)$$ of obtaining the tree $$T$$ in this way.

I can infer that $$p(T)$$ would not be necessarily equal to $$q(T)$$ but I can't seem to explain why. An example would help.

1. Any tree structure of size $$n$$ is a possible structure for a binary search tree on $$\{1, …, n\}$$. Since there are $$C_n = \frac{1}{n+1}\binom{2n}{n}$$ such trees (see Catalan numbers), if $$T$$ is a BST, we get $$p(T) = p_n=\frac{n+1}{\binom{2n}{n}}$$. For example, $$p_3 = \frac1{5}$$.
2. There are $$5$$ BST of size $$3$$, but $$6$$ permutations. That means that two of those permutations create the same BST. Indeed, $$(2, 1, 3)$$ and $$(2, 3, 1)$$ create the same tree $$T$$ such that $$q(T) = 2\frac16 = \frac13$$. For all other trees, $$q(T) = \frac16$$.