How to traverse a binary tree in O(n) time without extra memory

Question

Given a binary tree with an integer, Left & Right pointers, how can one traverse the tree in O(n) time and O(1) extra memory (no stack/queue/recursion)?

This guy gave a solution which is not O(n) total time that encoded the current path as an integer (and thus works on for trees of limited depth).

I am looking for the classical solution

(SPOILER)

that encoded the parent of each node in the children.

Answer 1

Any good algorithm book will have this algorithm, look e.g. in Knuth (TAOCP I.2.3.1 Traversing binary trees, excercise 21). However, because this algorithm modifies the tree in place, you must use extreme caution in a multi-threaded environment.

You might also use threaded trees (see in Knuth).

Answer 2

The main idea is similar to the list inversion algorithm, with one super-ugly tricky hack (from a theoretical point of view, probably a cheat), based on the fact that pointers are (in all langugae currently known to humans), 0 mode 4 as integers.

The idea is that you can flip the pointers on the path down the tree to point upwards. The problem is that - and this is where you divert from the list inversion algorithm - when you backtrack you need to know if left points up or right points up; at which point we use the hack.

Pseudo code follows:

current = root->left
next = current
while (current != null) {
  next = current->left
  current->left = static_cast<int>(prev) + 1 // ugly hack.
  current = next
}
status = done
while (current != root or status != done) {
  if (status = done) {
     if (static_cast<u32>(current->left) %4 = 1) {
         next = static_cast<u32>(current->left) -1
         current->left = prev
         status = middle
     }
     else {
         next = current->right
         current->right = prev
         status = done
     }
     prev = current
     current = next
  }
  else if (status == left) {
     if (current->left) {
       prev = current->left
       current->left = static_cast<u32>(next) +1
       next = current
     }
     else
       status = middle
  }
  else if (status == right) {
     if (current->right) {
        prev = current->right;
        current ->right = next;
        next = current
     }
     else
       status = done
  }
  else {// status == middle
     work_on_node(current)
     status = right
  }
}