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.
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.