Food for Thought: Random Binary Trees

In class, we saw treap, a form of random binary search trees where the priorities are chosen at random. Let us consider a different form of random trees.

Let $\pi$ be a random permutation of the elements of $\{1, \ldots, n\}$. Let $T_\pi$ denote the tree that results from inserting $\{1, \ldots, n\}$ into an initially empty BST in the order of appearance in $\pi$ using the standard BST insert rules (with no rotations). A tree $T$ that is sampled from the distribution of all such trees, uniformly over all permutations, is called a random tree.

Define the size of a node in a BST to be the number of elements in its subtree (including itself). Denote the sizes of the nodes $1, \ldots, n$ by $s_1, \ldots, s_n$.

There are several questions one can ask here:

1. Given a specific tree $T$, what is the probability of getting this tree $P[T]$ in terms of $s_i$'s?
   
2. Suppose we use the following insertion scheme (called INSERT$(i)$).
   After inserting element $i$ at a leaf using standard BST insert, traverse the access path upwards one node at a time.
   For each node $j$ encountered on this path, mark $j$ with probability $(1 + s_j)^{-1}$.
   Rotate $i$ with its parent until $i$ rotates over the highest marked node on the access path (and erase all marks).
   
   Now let $T$ be a BST with root $w$, left-subtree $T_L$ and right-subtree $T_R$.
   Define Join$(T_L, T_R)$ to be the set of trees that can be created
   by rotating nodes with $w$ until $w$ is a leaf, and then deleting $w$.
   Thus, Join$(T_L, T_R)$ is the set $\hat{T}$ of trees such that inserting $w$
   into $T' \in \hat{T}$ yields $T$ with some positive probability (convince yourself of this fact).
   
   Can we show that $P[T] \cdot n = P[T_L] \cdot P[T_R] = \sum_{T' \in Join(T_L, T_R)} P[T']$?
   
   
3. So then... this would imply that the sequence INSERT$(1), \ldots, $ INSERT $(n)$ will create a random tree in this sense.
   

We will post some solutions later :)