Take the 2-minute tour ×  Is it possible to iterate over a
binary tree in O(1) auxiliary space (w/o using a stack, queue,
etc.), or has this been proven impossible? If it is possible,
how can it be done?  Edit: The responses I've gotten about this
being possible if there are pointers to parent nodes are
interesting and I didn't know that this could be done, but
depending in how you look at it, that can be O(n) auxiliary
space. Furthermore, in my practical use case, there are no
pointers to parent nodes. From now on, please assume this when
answering.  share|improve this question I consider link to
parent as O(n) auxiliary space. You should edit your question to
explicitly mention your binary tree doesn't have such a
property. –  LeakyCode Apr 26 '09 at 15:35 How can you not have
pointers to your parent nodes? how can you iterate over your
tree at all without them? is that where the stack is coming in?
you will need parents pointers anyway to do balancing. – 
user82238 May 21 '09 at 22:15 add comment  10 Answe