I disagree. Expecting people to invent novel data structures on the fly, under stress, is unreasonable. Usually the idea is to ask a question they haven't actually seen, but is still somehow solvable using basic data structures most people learned in school, maybe with a minor tweak for the problem.
Otherwise, it's unlikely that most people will be able to solve it in 45 minutes, even with hints, and then you don't learn anything other than that they failed at an unreasonably hard problem.
So, one of the problem's solutions being a binary tree isn't itself necessarily a problem. The interview could be done well or badly depending on execution, and we can't judge that from afar. All we really know is that a binary tree was somehow involved.
---
At least, that's the idea. Interviewing is still terrible. It's pretty random to base a hiring decision on a few (extended) questions, and I think interviewers are left on their own too much to come up with good questions. How do we even know what's a good question or not?
Sometimes I wonder if it wouldn't be better to choose twice as many candidates as you need and pick half of them at random, just so everybody is clear that there's a lot of luck involved and they don't take either success or failure some kind of precise indicator of someone's worth.