Average height of a binary search tree

Question

How do you compute the average height of a binary search tree when adding 1000 random ints? What is the average height?

Answer 1

This question got me asking whether you can definitively work this out without actually generating the trees.

I managed to write an application which could calculate the answer to what the average height would be if you added every possible permutation of N unique numbers to a naively implemented binary tree.

The answers I got are in this graph. (The X-axis is the number of items in the tree, the blue line is the average height, and the red line is the optimum possible height)

N     Average Height
2     2
16    7.039
32    9.280
64    11.679
256   16.783
343   17.896

Granitebolshevik is right: it's possible but statistically unlikely that a naively implemented tree will be the optimum height, without extra balancing functionality.

The algorithm has a complexity of O(N^2), and it isn't fast enough to calculate really large numbers.