Is randomly building a BST different from random sampling whole trees?
You want to distinguish


  randomly built binary search tree


from


  choosing a binary search tree from a random distribution.


Let me first tell you why this is not a well-posed query. Neither version is
completely specified; the first misses the process by which the tree is built
as well as the used random source, the second lacks a specification of the
distribution to be used. In particular, the "randomly built" trees are
"chosen from a random distribution"!

Now I'll assume that you (or your teacher) made the "usual" assumptions and reformulate
the models.


Starting with the empty tree, we insert keys $s_1, \dots, s_n \in [1..n]$ 
successively (with BST insertion). The sequence is chosen uniformly at random 
from all permutations of $[1..n]$.

This is the famous random permutation model.
Pick a tree uniformly at random from all BSTs with keys $[1..n]$.


There are several ways to see that the two models define different random distributions.


There are $n!$ different permutations but only 
$C_n = \frac{1}{n+1} \cdot \binom{2n}{n}$ 
BSTs. Show that it is not possible to distribute the permutations evenly, 
i.e. $C_n$ does not (always) divide $n!$.

In particular, for $n=3$ we have six permutations but five BSTs.
For $n=3$, enumerate all trees and notice that four trees result from one
permutation each while the fifth results from two. Ergo, the random 
permutation model is not uniform.
Know (from earlier studies) that BSTs have average height $\Theta(\log n)$
in the random permutation model but $\Theta(\sqrt{n})$ in the uniform model.

The first is a standard result found in most textbooks on the matter. The latter, admittedly, a less known result by Flajolet and Odlyzko [1]; the method of analysis has broader relevance and the result generalises to many families of trees.





The average height of binary trees and other simple trees by P. Flajolet and A. Odlyzko (1982)