Randomly generated binary search trees case comparison

Question

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.

Answer 1

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$.