[bratfarrar]

People will occasionally try that, but my point to them is that they should be writing a general purpose BST, which should also allow degenerate trees. So no, I do try to steer people away from theoretically correct but desperately inefficient approaches.

[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.

[lzhou]

That's when the flustered interviewee can either fight (patch his solution) or flight (start all over using a class with refs). The most obvious patch is to use a large hashmap instead of a massive array. Still inefficient, but no longer that desperate (and actually has some added benefits).