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

  • $\begingroup$ Thanks...It is clearer now. $\endgroup$
    – Mike
    Nov 22, 2022 at 15:28
  • $\begingroup$ @Mike Consider accepting the answer if you are satisfied with it! $\endgroup$
    – Nathaniel
    Nov 22, 2022 at 15:57
  • $\begingroup$ @ Nathaniel Done. Thanks $\endgroup$
    – Mike
    Nov 22, 2022 at 16:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.