Saturday, October 31, 2009

Combined Pre-Order and Post-Order Traversal: A Stackless Approach

Here's a slight mod to my previous code which gets rid of the stack altogether. It just relies on the parentNode link present in all nodes in a DOM tree. Performance is comparable. Memory usage is less - of course, we don't have a stack anymore.

public function traverse($root) {
// Start at document root
$_flag=FALSE;
$_node=$root->documentElement;
// Repeat until we reach the top
while ($_node) {
if (!$_flag) {
/* Insert pre-order sequence here */

if ($_node->firstChild) {
// Descend to branch
$_flag=FALSE;
$_node=$_node->firstChild;
continue;
}
}
/* Insert post-order sequence here */

// Reset flag
$_flag=FALSE;
if ($_node->nextSibling)
$_node=$_node->nextSibling;
else {
// Ascend to parent node
$_flag=TRUE;
$_node=$_node->parentNode;
}
}
}

Like it's predecessor, it doesn't need a "visited" flag attached to its nodes. The $_flag variable here is key to how it works. It is a simple toggle to indicate whether we're moving down/right along a branch (FALSE) or ascending the tree (TRUE).

Now we have a state machine without the extra baggage.

No comments:

Post a Comment