algorithm - Iterating over a Binary Tree with O(1) Auxiliary Space

Question

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.

Answer 1

Geez, I'll have to actually type it up from Knuth. This solution is by Joseph?M.?Morris [Inf.?Proc.?Letters?9?(1979), 197-200]. As far as I can tell, it runs in O(NlogN) time.

static void VisitInO1Memory (Node root, Action<Node> preorderVisitor) {
  Node parent = root ;
  Node right  = null ;
  Node curr ;
  while (parent != null) {
    curr = parent.left ;
    if (curr != null) {
      // search for thread
      while (curr != right && curr.right != null)
        curr = curr.right ;

      if (curr != right) {
        // insert thread
        assert curr.right == null ;
        curr.right = parent ;
        preorderVisitor (parent) ;
        parent = parent.left ;
        continue ;
      } else
        // remove thread, left subtree of P already traversed
        // this restores the node to original state
        curr.right = null ;
    } else
      preorderVisitor (parent) ;

    right  = parent ;
    parent = parent.right ;
  }
}

class Node
{
  public Node left  ;
  public Node right ;
}