My answer was, "I don't know; I would look it up in a book. Is this really relevant for an architect position?" I got the offer anyway and turned it down.
I think these technical interview questions are a silly way to evaluate developers. You almost never have to write low-level sort routines because you just call them in runtime libraries. But it's harder to evaluate the more important ability to modularize code and manage complexity.
In my opinion, it's a somewhat misleading question (or the answer is creative to the point of stretching definitions).
In-order traversal is pretty easy without a stack, if every node keeps track of its parent.
1. go down left branches until you get to a leaf.
2. visit leaf, and go up.
3a. if, in going up, you were at a left child, visit this node, then go right. loop to 1.
3b. if, in going up, you were at a right child, go up again. loop to 3.
3c. if you can't go up, you're done.
The trick comes from not really storing the parent pointer at each node, but instead doing trickery with xor-ing various addresses together so that you can store 3 pointers in the space of 2 (plus possibly an extra bit).
Of course, if you do so, you've constructed something that's not exactly a binary tree, and can only be traversed in certain fashions where you'll always have the necessary information to xor.
