Average height of a BST with n Nodes

I have to find the maximum, minimum, and average height of a BST with n nodes. After doing some researching I found that the maximum height is $n-1$ and the minimum height is $\log_2(n+1)-1$. My question is how do I get the average height of a BST with n nodes?

• What have you tried so far? Have you read: sciencedirect.com/science/article/pii/0022000082900046 ?
– Evil
Aug 21 '18 at 0:21
• Since you can put any values into BST nodes, I think it's the same question as cs.stackexchange.com/questions/2762/… . That said, I never seen exact answer to this question, but it is well known that search in BST on average is O(log n), and the average height probably too. Aug 21 '18 at 0:24
• Where is the randomness from? For example, is the tree built by inserting $n$ random ints? Aug 21 '18 at 11:24
• A similar stuff also given in CLRS Theorem 12.4 Mar 16 '21 at 13:52

• $X_n$ height of a tree composed of $n$ nodes.
• $Y_n = 2^{X_n}$ is referred to as the exponential height.
One of the BST's properties is that the left subtree must contain key values less than the root. Also, the right subtree contains key values greater than the root. This property is recursive so it applies to any node. Having said that, pick any node at random, call it the $i^{th}$ node, then, the left subtree has $i-1$ elements and the right subtree has $n-i$ elements. Therefore, $$Y_n = 2 \max (Y_{i-1},Y_{n-i})$$ Assuming all nodes are picked with equal probability, so picking a node $i$ has the following probability $$Pr(i) = \frac{1}{n} \quad \forall i=1\ldots n$$ Now, let us find the expected value of $Y_n$ \begin{align} E(Y_n) &= E[2 \max (Y_{i-1},Y_{n-i})]\\ &= 2 \sum\limits_{i=1}^n Pr(i)E[\max (Y_{i-1},Y_{n-i})] \\ &= \frac{2}{n} \sum\limits_{i=1}^n E[\max (Y_{i-1},Y_{n-i})] \\ &\leq \frac{2}{n} \sum\limits_{i=1}^n E(Y_{i-1}) + \frac{2}{n} \sum\limits_{i=1}^n E(Y_{n-i}) \\ &= \frac{2}{n} \sum\limits_{i=0}^{n-1} E(Y_{i}) + \frac{2}{n} \sum\limits_{i=0}^{n-1} E(Y_i) \\ &= \frac{4}{n} \sum\limits_{i=0}^{n-1} E(Y_i) \end{align}
Now, by induction, you can actually prove \begin{equation} E(Y_n) \leq \frac{1}{4} C_{n+3}^3 \end{equation} Remember that we have \begin{equation} 2^{X_n} = Y_n \end{equation} or \begin{equation} E(2^{X_n}) = E(Y_n) \end{equation} Using Jensen's inequality, we can say that \begin{equation} 2^{E(X_n)}\leq E(Y_n) \end{equation} But \begin{equation} E(Y_n) \leq \frac{1}{4} C_{n+3}^3 \end{equation} So \begin{equation} 2^{E(X_n)}\leq E(Y_n) \leq \frac{1}{4} C_{n+3}^3 \end{equation} And note that \begin{equation} C_{n+3}^3 = \frac{(n+3)!}{3!n!} = \frac{(n+3)(n+2)(n+1)}{6} \sim O(n^3) \end{equation} So \begin{equation} 2^{E(X_n)} \leq O(n^3) \end{equation} Take log on both sides, \begin{equation} E(X_n) \leq O(\log n^3) = O(3 \log n) = O(\log n) \end{equation} Therefore, the average BST height is of order $O(\log n)$, which is what you'd expect out of Binary stuff, right ?