# 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)$ Commented Jan 5, 2011 at 22:37
• The $lg(n)$ bound is only obtained when you build a binary search tree, not a random binary tree. Commented Jan 9, 2011 at 14:01

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.