I need some help with the following question.
Given the random permutations of $ n > 2 $ numbers. Now, creating a binary search tree and puting it the organs one by one.
Denote the input organs by $ a1< ... <an $ .
a. $ \forall \:\: 1 \leq i \neq j \leq n $ calculate the probability that $ ai $ is the predecessor of the $ aj $ in the generated tree.
b. $ \forall \:\: 1 \leq i \leq n $ calculate the mean depth of the $ ai $ in tree generated tree.
And in addition, calculate the mean of the successors number of the $ ai $ in tree generated tree.
Thanks in advance