Exercise 12.4.3

Show that the notion of a randomly chosen binary search tree on $n$ keys, where each binary search tree of $n$ keys is equally likely to be chosen, is different from the notion of a randomly built binary search tree given in this section. (Hint: List the possibilities when $n = 3$.)

With the elements 1, 2 and 3, there are only $5$ possible binary search trees:

1             1            2           3           3
  \             \        /  \        /           /
    2             3     1    3      1          2
      \         /                    \       /
        3     2                       2     1

There are, however $3! = 6$ by the definition of the chapter.