It depends on how you look at it.

Google wants people who have a strong understand of CS fundamentals (which includes knowing core data structures). Google also wants people who are good coders (which includes being able to translate an idea into code).

A good coder who knows CS fundamentals should be able to do that. Thus, not knowing how to implement a binary search tree is revealing.

And, really, the question is rarely "implement a binary search tree." It may, however, be to implement a binary search tree which support a getMedian() operation.