What, to me, the relevant part of the question would be is that given some datastructure in the code base, you are constantly aware of the performance characteristics of the structure, so you can make an informed decision on how to do something.
I can certainly understand asking to make a binary tree as a quick refresher to have the interview candidate in the datastructures mindset - and even don't mind if they mess it up, as long as they know the performance characteristics once they have one in hand.
Especially for a senior position where you will be more likely to spend time deciding on what the architecture will look like, I would want to make sure that the candidate would be able to make an informed call.
And sometimes, part of an interview is to learn where someones limitations may lie. Even if datastructures isn't their strong suit, the candidate may be suitable for the position, but it's still important to know that the candidate has limitations on that subject.
So the candidate went ahead and "failed" datastructres. Fine, they can make up for that. The candidate proceeds to make up for it by becoming frustrated with the interviewer, and resolves that frustration by anger and hostility. That is the point where I would not want that person on the team.