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.