Is there something special about reversing a binary tree?
AFAIK, you could swap the child pointers and do that recursively for the child nodes. You could also do things O(1) by just changing the comparison function, perhaps by wrapping it to negate the comparison.
This is a specific, well-known case. Max Howell (the author of Brew) was rejected by Google. One of his interviewers asked him to invert a binary tree.
