What is the average asymptotic depth of a simple unbalanced search tree?

Question

For a balanced search tree, it is O(log(N)) for all cases. For unbalanced search trees, the worst case is O(N), e.g., insert 1, 2, 3, 4,.. and best case complexity is when it is balanced, e.g., insert 6, 4, 8, 3, 5 7. How do we define the average case complexity for unbalanced search tree?

Answer 1

The average height of Binary Trees is Theta(sqrt(n)). This has been shown (or referenced, not very sure) in the following paper: http://www.dtc.umn.edu/~odlyzko/doc/arch/extreme.heights.pdf.

But perhaps you are more interested in the average depth of a random node and this is Theta(log n), as can be seen here: http://www.toves.org/books/data/ch05-trees/index.html (Section 5.2.4).