Many of the interviews could actually work if they broke the process down into 8 questions instead of one (how would you represent a tree? a binary tree? how would you find node X? how would you move node X to the other side of the tree?). But, the ability to accommodate understanding takes empathy and human connection, not being a jerk programmer on interview duty who is browsing HN while listing to the interviewee mumble on your speakerphone.
Never underestimate the lack of ability in the interviewer and not the interviewee. Except, the company always believes itself to be more competent than outsiders, so you're ultimately left with being condescended to unnecessarily.
Whatever! They asked me back but it sure is a frustrating feeling even if I tend not to appear flustered until I walk out, introspect, and realize what a doofus I was.
They don't just stop at binary trees. Think of it more like memorizing hundreds of magic tricks that could be done using a deck of cards. The tree is more analogous to those deck of cards. The data structure remains constant but the tricks you can do keep changing.
I know of situations where candidates have been grilled whole full hours on tree traversal methods, and then asked to code up perfectly working solutions for them.
Do these people seriously think people who can invent 50 years of CS research by sheer analysis over an hour on the whiteboard, will be ready to work for them to write shell scripts? If not you are only testing memory skills.
One thing that I'd recommend to anyone seeking any kind of job is taking some improv courses--they are pretty common in major centers and even some smaller towns, and can really improve your ability to deal with this kind of nonsensical interview situation, which tests a bunch of skills that have nothing to do with your ability to actually do the job.
The answer was transactions (database). You never forget that sort of mistake.