# Is randomly building a BST different from random sampling whole trees?

What is the difference between a randomly built binary search tree (using n keys )and choosing a binary search tree (of n key) from a random distribution

• What are your thoughts? If you think about the issue for a minute, it should become obvious that randomly building specifies one probability distribution over BSTs -- there are others.
– Raphael
Nov 14, 2014 at 11:18

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.

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

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

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

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

3. 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 ; the method of analysis has broader relevance and the result generalises to many families of trees.

1. The average height of binary trees and other simple trees by P. Flajolet and A. Odlyzko (1982)
• Which results in Flajolet & Odlyzko's paper are you pointing at? The only mention of BST I can find therein is from other papers. Also, what's the reference for the second part of 3.? This would give substance to the claim on Wikipedia that "after a long intermixed sequence of random insertion and deletion, the expected height of the tree approaches square root of the number of keys," which is quite puzzling. Sep 24, 2019 at 3:43
• @Michaël The main result of the paper. Note that you can disregard the keys when averaging in the uniform model.
– Raphael
Sep 28, 2019 at 23:15

Randomly built binary search tree : When binary tree is built by picking n keys one by one randomly from a set of keys.

While binary search tree from a random distribution mean there are all possible ways of binary tree with n keys from a set of keys . and you are picking directly one of the tree.

Only way of making a random binary tree is different.

Randomly built binary search tree will be more efficient to make than the later one.

but both will result in estimated search time of O(log n)

• I thought so too. But after reading on wiki [en.wikipedia.org/wiki/Random_binary_tree] about uniformly binary tree, I got confused. It says that the avg depth is proportional to n^1/2 rather than to log n. From where did this number arrive? Oct 15, 2014 at 7:28
• Will have to do check this using math. O(log n) was my intuition. I think after exact calculation of estimated depth for both.... answer may differ.. Oct 15, 2014 at 7:35
• How to calculate the estimated depth for randomly selected binary search tree? Oct 15, 2014 at 7:36
• Total possible binary search tree with n nodes= catalan number.. this thing can help you calculate the estimate Oct 15, 2014 at 7:40
• No idea how to proceed on that one Oct 15, 2014 at 8:12