I am, almost, a 20 year industry veteran. I have no problem being asked to run the gauntlet. I'm happy for a chance to demonstrate my skills. Candidates that expect some sort of preferential treatment due to the number of years they have been working arouse my suspicions.
But don't expect a senior dev to have red-black trees memorized. A senior dev's answer will be "Use the library implementation. If there isn't one, look for one online I can use. If there isn't even one of those, look it up in Knuth." With no apology whatsoever for not knowing how to do it off the top of their head, because they know they don't need to do that.
I don't expect anyone to have red-black trees memorized. But I do expect an engineer at any level to be able to, say, rebalance a binary tree through brute force.
I have to admit, my initial reaction was about the same as yours. But after a minute or two of thought, I did know how to do it, even though I haven't ever (directly) used a binary tree in 30 years as a professional software engineer.
I don't think it's out of line to expect a senior person to have the breadth of knowledge to be able to work, at a basic level, with basic data structures. To have memorized all the details of stuff they don't use? No. To have a basic knowledge? Yes.
