Yes, to minimize the depth by "filling" every branch possible/equalizing the number of nodes in every subtree at a given depth.

>Are you referring to writing your own implementation of AVL or RB trees?

Yes, though the interviewer didn't say "AVL" or "RB". I'm not sure I ever even got a class with those in it, and frankly, I don't care enough to memorize how to implement them just for an interview question.

Again, this wasn't Google. This wasn't a firm that did complicated data-structures stuff all the time. They fully admitted how simple their work is. But they asked about how to balance a binary search tree anyway.