Geometric / Visual explanation that the average height of a random binary tree of given size $n$ is asymptotically $2\sqrt{\pi n}$

I just finished reading the proof that the average height of a random binary of given size $n$ is asymptotically $2\sqrt{\pi n}$.

I'm now searching for an intuitive, or geometric, or visual proof of this asymptotic equivalence. In other words, I'm trying to find an intuitive arguments that shows that this number grows like $\sqrt{n}$.

Any ideas?
Thanks!

-
According to en.wikipedia.org/wiki/Random_binary_tree this is dependent on how you select a random tree. If you pick one out of all the trees of size n it does scale with $\sqrt{n}$. If you build it up in another way, it is $\log(n)$ – Ross Millikan Jan 5 '11 at 22:37
The $lg(n)$ bound is only obtained when you build a binary search tree, not a random binary tree. – CFP Jan 9 '11 at 14:01

1 Answer

Here's one way to at least guess the growth rate. A random binary tree of size $n$ is the same thing (plus or minus one) as a random walk on the non-negative integers of length $n$ starting and ending at $0$, with the height of the tree corresponding to the farthest the walk goes from $0$. The order of magnitude of the height should behave like the order of magnitude of the related problem of looking at the ending position of a random walk on the integers of length $n$ starting at $0$. (I don't know how to justify this rigorously but it seems pretty plausible to me.)

But this question is much easier, since now it's a sum of independent Bernoulli random variables. The expected end position is $0$, but it is straightforward to calculate that the variance in the end position is $n$, so the standard deviation is $\sqrt{n}$. Of course, since we're dealing with a sum of independent Bernoulli random variables, we can be much more precise because the central limit theorem applies. The point is that this probabilistic reasoning tells us what the right growth rate to expect is: it's also the same rate that crops up in Brownian motion.

-
Thanks =) This is actually pretty close to the actual proof, but I was searching for something... more visual perhaps =) +1 anyway ;) – CFP Jan 9 '11 at 14:02
@CFP: the computation of the variance of a sum of independent random variables is essentially a form of the Pythagorean theorem, so if you want to you can visualize this computation in terms of the spiral of Theodorus: en.wikipedia.org/wiki/Spiral_of_Theodorus – Qiaochu Yuan Jan 9 '11 at 14:09
Thanks, that's extremely interesting, and extremely useful too =) – CFP Jan 9 '11 at 14:15
Hi there! After more careful thinking, I think that you might be calculating here the average length of a path in the tree, instead of the length of the longest branch. Although the asymptotic equivalent is the same, the problem is slightly different (and the solution can here be easily obtained by considering formal series. So I wonder if your explanation does apply here... Not sure =) – CFP Jan 14 '11 at 20:46
@CFP: I never claimed that this was a solution to the problem! I just said this was a way to guess the right growth rate. – Qiaochu Yuan Jan 14 '11 at 20:53