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

Answer 3

That guy's algorithm is interesting, but it needs to be pointed out that it does require O(log n) extra bits of space to traverse a binary tree with n nodes. Space requirements must be measured in bits, not bytes -- usually they collapse into the same thing when Big Oh notation is used, but cases like this point out why it's important to make the distinction.

To see this, ask how a tree with more than 2^32-1 nodes can be traversed using a single integer of storage (on a 32-bit platform).

Answer 4

Use O(1) storage to remember a "last node visited" pointer. You can initialize it to 0 or some unknown value.

To walk the tree, start at the root node. Look at both of the node's children. If your "last visited node" is equal to the RIGHT node, then step to the parent node. If the "last visited" is equal to the LEFT node, then step to the right node. Else step to the left node.

Repeat until you've finished walking the whole tree. The only real cleverness is using the one variable to remember where you're coming from in order to decide where to go next. This makes the traversal deterministic.

You'll end up taking O(n) steps. You'll visit every middle node three times, and every leaf once, so you're still O(N). Storage is O(1).

Answer 5

Here is another solution

http://sites.google.com/site/debforit/efficient-binary-tree-traversal-with-two-pointers

But I was wondering if there is a way to do this in languages like Java which DO NOT have pointers in true sense.