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
// Repeat until we reach the top
while ($_node) {
if (!$_flag) {
/* Insert pre-order sequence here */

if ($_node->firstChild) {
// Descend to branch
/* Insert post-order sequence here */

// Reset flag
if ($_node->nextSibling)
else {
// Ascend to parent node

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