A binary tree is just a tree data structure where each node has at most two children. And that's dead simple and every programmer should be able to implement that when aksed. Note that it doesn't even have the search (i.e. sorted) requirement and much less the self-balancing one. You can work your way towards that with the right questions and that would be an acceptable way to structure an interview. Start with something simple everyone should be able to do and then work your way up the requirements and discuss potential problems/pitfalls and their solutions.
Nobody talked about implementing a specific variant of a red-black tree when the general topic of self-balancing binary search tree hasn't even be mentioned.
To add to that, a binary tree is often not really "implemented" but simply encoded in an array. That is, the children of any given node i are 2i and 2i+1 in the array.
So depending on the actual exercise/interview question you might able to just show that, especially of you have to use pseudo code.
Correct me if I'm wrong, but isn't this exactly the case where you don't want an unbalanced tree? A degenerate tree is bad enough; a degenerate tree implemented as an array in this way is catastrophic. So it seems to me that if you're refining the topic further in some sort of talk, the topic of balancing should precede the topic of physically representing the tree as an array.
It all depends on the specific topic. If I just want to store my data in binary tree structure without the possibility of deletes and just with an insertion-order requirement, then the tree is automatically balanced and using an array like that is totally fine. The use-cases are probably rare (I can't think of a situation from the top of my head), but binary tree doesn't have to mean search tree.
The self-balancing part is usually added after the search part as balance is trivial/unimportant when the order/position of the elements has no constraints.
> The use-cases are probably rare (I can't think of a situation from the top of my head)
I imagine there's quite a lot of them. Things like VP-trees and such get often built statically and could be implemented in a similar way. Not sure if the simple (2i, 2i+1) schema is optimal for this but perhaps it could be adapted.
It is dead simple. What you're describing (two children, no constraints) is basically a cons cell. Yet I suspect that most people don't use cons cells as binary trees. Which is probably why I didn't understand that apparently rather nebulous topic as being this generic.
This is another point in which this can be a good interviewing question. For certain jobs you don't want someone who just forges ahead with an unclear specification.
That said, for most dev jobs implementing a binary tree isn't necessary knowledge. But if I need a dev who can get their hands dirty I would be weary of hiring someone who can't take a decent stab at it during an interview.
