[dalke]

To be fair, it's "desperately inefficient" only in the face of unbalanced trees, no? Which mostly only happens for unrealistic scenarios.

As stated, the problem assumes that time lookup isn't important, even though someone who wants a BST almost certainly chose it to get faster than linear lookup along with fast insert/delete operations and ordered searches. (Otherwise, why not use a hash table?) A self-balancing tree gives that additional guarantee, and in that case an array-based data storage won't be "desperately inefficient".

Indeed I suspect an array will be competitive or even better than an object based version, where each object has its own pointer overhead and associated memory fragmentation.

At the very least, the early AVL work in the 1960s used a tape for storage, and I suspect they didn't waste all that much tape space.

So someone's intuition from real-world use of BSTs might end up giving you a false negative.

[detrino]

If you need memory efficiency you can just use a B-Tree, which also has the advantage of being more cache efficient.