I like to give slightly more difficult versions of these questions as take-home problems, rather than interview problems. Give them out after phone screen, but before in-person interview.

And yes, something involving a binary tree order traversal would be the kind of thing that I'd be interested in. Because I want to work with programmers who can code, who at the very least know what recursion is and are able to employ it in the solution to a problem.

Concrete example: the startup I'm at has an expression editor. Expressions are tree structured. Typing an expression tree involves a post-order traversal. If there's an error in the validation, I need the programmer who's working on it to not be phased by these simple concepts. This typing currently happens in an async background task in Java, but it could give a better experience to the end user if it occurred in JS on the client's machine. This stuff just got really relevant after coffee.

But more importantly, I want to see what kind of code - how convoluted or not, how elegant or not, etc. - the person writes. I want to know what kind of code I'm going to see in pull requests, and how much of a PITA it's going to be to get them up to scratch.

Standard engineering stuff like unit tests can be taught. Writing tight, readable and elegant code is much more difficult.