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

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.