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, loop-back to the "previous" node. This previous node is the one that would visited just prior to this one in a in-order visitation. For make the explanations easier to follow we can define the "rank" of a node as the in-order position of this node during the in-order visitation. So a node would have have "rank" equals to the number of node on the left sub-tree plus the rank of the parent if this node is the right child of the parent.
The visitation start by toggling this loop-back 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 sub-tree with smaller values that now contains one loop-back. When ever the toggling of the loop-back removes a loop-back, 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 re-applied on this parent node the loop-back 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 sub-tree 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.
in-order visit
Since the loop-backs are toggled based on the ranks of an in-order visit this meas that when ever a node has it’s loop-back 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 sub-tree :
visit current node
current = current->right
pre-order visit
typical pre-order 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 loop-back creation, instead of doing so on removal. Since the first thing that is done on a root of a sub-tree 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 :
pre-order visit current node
current = current->left
case current is largest of sub-tree :
pre-order visit current node
current = current->right
case loop_back removed :
current = current->right
post-order 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 loop-back 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, in-order and pre-order. 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 loop-back that was previously created was removed. This returns a sub-tree 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