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