How to calculate the average depth of a binary tree? My professor has said that the average depth of all possible binary trees which can be formed with $n$ nodes would be $O(\sqrt n)$ and has assigned the proof of this as homework. How do I approach this problem?
You haven't stated which distribution of random binary trees you are interested in, but in many cases the answer is indeed $\Theta(\sqrt{n})$. See for example Flajolet and Odlyzko, The average height of binary trees and other simple trees.