Proof that a randomly built binary search tree has logarithmic height

How do you prove that the expected height of a randomly built binary search tree with $n$ nodes is $O(\log n)$? There is a proof in CLRS Introduction to Algorithms (chapter 12.4), but I don't understand it.

• Which question? What example? Please edit and give full details. – Ran G. Oct 27 '12 at 19:54
• Please avoid using abbreviations (such as BST) and assume that most of us don't have the CLRS book. If you could copy the theorem here, and explain what is it that you don't understand, you will get more answers. – Ran G. Oct 27 '12 at 20:06
• This is going to depend on how the binary search tree is built. (Even if the result doesn't, the proof will.) Some more details would be useful. – Peter Shor Oct 28 '12 at 13:12

Let's first think about this intuitively. In the best-case scenario, the tree is perfectly balanced; in the worst-case scenario, the tree is entirely unbalanced:

Starting from the root node $p$, this left tree has twice as many nodes at each succeeding depth, such that the tree has $n=\sum_{i=0}^{h}2^i =2^{h+1}-1$ nodes and a height $h$ (which is in this case 3). With a little math, $n\le2^{h+1}-1\rightarrow h\le\lceil\log_2(n+1)-1\rceil\le\lfloor log_2 n\rfloor$, which is to say it has $O(\log n)$ height. For the entirely unbalanced tree, the height of tree is simply $n-1\rightarrow O(n)$. So we have our bounds.

If we were constructing a balanced tree from an ordered list $\{ 1,2,\dots,n\}$, we'd choose the middle element to be our root node. If we are instead randomly constructing a tree, any of the $n$ nodes are equally likely to be picked and the height of our tree is: $$height_{tree}=1+\max (height_{left\space subtree}, height_{right\space subtree})$$ We know that in a binary search tree, the left subtree must only contain keys less than the root node. Thus, if we randomly choose the $i^{th}$ element, the left subtree has $i-1$ elements and the right subtree has $n-i$ elements, so more compactly: $h_n=1+\max (h_{i-1},h_{n-i})$. From there, it makes sense that if each element is equally likely to be picked, the expected value is just the average of all cases (rather than a weighted average). Hence: $\operatorname{E}[h_n]=\frac{1}{n}\sum_{i=1}^{n}[1+\max (h_{i-1},h_{n-i})]$

As I'm sure you've noticed, I've deviated slightly from how CLRS proves this, because CLRS uses two relatively common proof techniques that are disconcerting for the uninitiated. The first is to use exponents (or logarithms) of what we want to find (in this case height), which makes the math work out a little more cleanly; the second is to use indicator functions (which I'm just going to ignore here). CLRS defines the exponential height as $Y_n=2^{h_n}$, so the analogous recurrence is $Y_n=2\times\max (Y_{i-1},Y_{n-i})$.

Assuming independence (that each draw of an element (out of the available elements) to be the root of a subtree is irrespective of all previous draws), we still have the relation: $$\operatorname{E}[Y_n]=\sum_{i=1}^{n}\frac{1}{n}\operatorname{E}[2\times\max (Y_{i-1},Y_{n-i})]=\frac{2}{n}\sum_{i=1}^{n}\operatorname{E}[\max (Y_{i-1},Y_{n-i})]$$ for which I did two steps: (1) moving the $\frac{1}{n}$ outside because it is a constant and one of the properties of summations is that $\sum_i ci=c\sum_i i$, and (2) moving the 2 outside because it is also a constant and one of the properties of expected values is $\operatorname{E}[ax]=a\operatorname{E}[x]$. Now we're going to replace the $\max$ function with something larger because otherwise simplifying is difficult. If we argue for nonnegative $X$, $Y$: $\operatorname{E}[\max(X,Y)]\le\operatorname{E}[\max(X,Y)+\min(X,Y)]=\operatorname{E}[X]+\operatorname{E}[Y]$, then: $$\operatorname{E}[Y_n]\le\frac{2}{n}\sum_{i=1}^{n}(\operatorname{E}[Y_{i-1}]+\operatorname{E}[Y_{n-i}])=\frac{2}{n}\sum_{i=0}^{n-1}2\operatorname{E}[Y_{i}]$$ such that the last step follows from the observation that for $i=1$, $Y_{i-1}=Y_{0}$ and $Y_{n-i}=Y_{n-1}$ and going all the way to $i=n$, $Y_{i-1}=Y_{n-1}$ and $Y_{n-i}=Y_{0}$, so every term $Y_0$ to $Y_{n-1}$ appears twice, so we can replace the entire summation with an analogous one. The good news is that we have a recurrence $\operatorname{E}[Y_n]\le\frac{4}{n}\sum_{i=0}^{n-1}\operatorname{E}[Y_{i}]$; the bad news, is that we're not much further than where we started.

At this point, CLRS pulls an induction proof $\operatorname{E}[Y_n]\le\frac{1}{4}\binom{n+3}{3}$ out of their ... repertoire of mathematical experience, one that includes an identity $\sum_{i=0}^{n-1}\binom{i+3}{3}=\binom{n+3}{4}$ they leave to the user to prove. What's important about their choice is that its largest term is $n^3$, and recall that we are using exponential height $Y_n=2^{h_n}$ such that $h_n=\log_2n^3=3\log_2n\rightarrow O(\log n)$. Perhaps someone will comment why this particular binomial was chosen. The general idea though is to bound from above our recurrence with an expression $n^k$ for some constant $k$.

To conclude with a one liner: $$2^{\operatorname{E}[X_n]}\le \operatorname{E}[Y_n]\le \frac{4}{n}\sum_{i=0}^{n-1}\operatorname{E}[Y_i]\le\frac{1}{4}\binom{n+3}{3}=\frac{(n+3)(n+2)(n+1)}{24}\rightarrow \operatorname{E}[h_n]=O(\log n)$$

• WOW.THANKS !!!! Even though i don't know about Expected value, this sort of makes sense. I did not do a discreet math course before doing algorithms. I will post more comments, if i have some doubt. Thank you Merbs. – user1675999 Oct 29 '12 at 0:12
• but why exactly is exponential height less than or equal the chosen binomial? I still don't understand why can't we choose any other binomial with different largest term and do exactly the same math... probably I'm stupid but I just can't see why ... and up to this point proof makes perfect sense, then they just had to pull something completely out of the blue and with no explanation tell us it "proves" them being right... – Zeks Dec 29 '13 at 16:21
• @Zeks So, we can choose other binomials with larger terms. If the term is still polynomial (n^k), the conclusion is the same because the k is dropped in the big-O notation (the way 3 was dropped). But if we substituted in something exponential (e^n), it would still be a correct upper bound, just not a tight one. We know that the expected height is at least logarithmic, so determining that it is at most logarithmic makes it tight. – Merbs Dec 31 '13 at 0:06
• @DavidNathan I don't understand your concern - are you doubting that 1/n is a constant or that it can be moved outside the summation? It, like the constant 2, is largely taken out for illustrative purposes, to simplify the remaining proof. – Merbs Apr 30 '16 at 0:22