Visit a tree in O(1) space
This article is intended so one (me) can better undestand the agorithm By Knuth.
The idea here is to toggle, create or remove, loopback to the "previous" node. This previous node is the one that would visited just prior to this one in a inorder visitation. For make the explanations easier to follow we can define the "rank" of a node as the inorder position of this node during the inorder visitation. So a node would have have "rank" equals to the number of node on the left subtree plus the rank of the parent if this node is the right child of the parent.
The visitation start by toggling this loopback from the node with the previous rank to this. If there’s no element with smaller ranks than the current the visitation continues to the right to visit larger elements. Otherwise the loop is created and the visitation goes left to a subtree with smaller values that now contains one loopback. When ever the toggling of the loopback removes a loopback, instead of creating it, this means that all elements that are smaller than the current were already visited so we need to go right. The pseudo code bellow shows the whole process.
The whole thing works because whenever we reach a leaf node, this node was already connected with a parent with the next ranked element so going right from it means going up on the tree to the next ranking node. When the algorithm is reapplied on this parent node the loopback is removed, signaling that the visitation will go on to the right instead of left.
current = root while (current is not null) toggle_loop_back_from_previous(current) case loop_back created then current = current>left case loop_back removed or current is largest of subtree then current = current>right
This will walk through all the nodes on the tree, but we need to detect when we need to visit the nodes for different types of visiting strategies.
inorder visit
Since the loopbacks are toggled based on the ranks of an inorder visit this meas that when ever a node has it’s loopback removed we can safely visit it. This will visit all the nodes that have a well defined previous node. To fix this we need to visit the nodes that have no left children.
current = root while (current is not null) toggle_loop_back_from_previous(current) case loop_back created then current = current>left case loop_back removed or current is largest of subtree : visit current node current = current>right
== preorder visit
typical preorder visit will visit first the root node before recusring into left then right. To emulate this form of visitor we need to visit the current node on loopback creation, instead of doing so on removal. Since the first thing that is done on a root of a subtree is this exact creation, before moving on to the left. Nodes that have no left branch will still be visited.
current = root while (current is not null) toggle_loop_back_from_previous(current) case loop_back created : preorder visit current node current = current>left case current is largest of subtree : preorder visit current node current = current>right case loop_back removed : current = current>right
postorder visit
This traversal ordering is not possible using this technique. The problem is that for doing this type of traversal both child have to be visited before the root is visited, but once the loopback is removed the root node is never going to be visited again but all the nodes on the right tree are yet to be visited at this point.
full C++ implementation
This implementation will make both visits that are possible using this technique, inorder and preorder. All the functions that are in anonymous namespaces are internal only and can be seen as implementation details.
The function that toggles the loop_back returns a status enumeration that indicate what actions was taken:

NO_ACTION : this node has no children with rank smaller than it self.

LOOPBACK_CREATED : the node with rank just bellow the current rank was connected to the root.

LOOPBACK_REMOVED : the loopback that was previously created was removed. This returns a subtree into it’s original form.
#ifndef VISIT_TREE_H_INCLUDED
#define VISIT_TREE_H_INCLUDED
#include "tree.h"
namespace {
enum ToggleResult {
NO_ACTION,
LOOPBACK_CREATED,
LOOPBACK_DELETED
};
ToggleResult toggle_loop_back(node_ptr start);
}
template<class VISITOR1, class VISITOR2>
void visit(node_ptr& root, VISITOR1 preorderVisitor, VISITOR2 inorderVisitor) {
node_ptr current = root;
while (current) {
switch(toggle_loop_back(current)) {
case LOOPBACK_CREATED:
preorderVisitor(current>get_value());
current = current>get_left();
break;
case NO_ACTION:
preorderVisitor(current>get_value());
// spill over.
case LOOPBACK_DELETED:
inorderVisitor(current>get_value());
current = current>get_right();
}
}
}
namespace {
node_ptr find_rightmost_of_left(node_ptr start);
ToggleResult toggle_loop_back(node_ptr start) {
if (!start  !start>get_left()) {
return NO_ACTION;
}
node_ptr current = find_rightmost_of_left(start);
// Is this a loop?
if (current>get_right() == start) {
current>get_right().reset();
return LOOPBACK_DELETED;
} else {
current>get_right() = start;
return LOOPBACK_CREATED;
}
}
node_ptr find_rightmost_of_left(node_ptr start) {
node_ptr end = start;
if (!start  !start>get_left()) {
return start;
}
start = start>get_left();
while(start>get_right() && start>get_right() != end) {
start = start>get_right();
}
return start;
}
}
#endif