Skip to main content

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.

Comments

Post a Comment

Popular posts from this blog

Lightweight Javascript and CSS compressor / minifier written in PHP

People who know me well are aware that I have an obsession for minimalism and code elegance. It seems like there are only a few Javascript and CSS compressors available on the Web. A handful of code is written in PHP. And even less - "original" code that isn't a port of JSMin, YUI compressor or Dean Edwards' Packer. So I decided to publish my code, which is really a fragment and an integral part of the PHP Fat-Free Framework and it follows the same GPL3 license. The basic feature that Javascript and CSS compressors have in common is the ability to strip whitespaces and comments off your files, thus reducing the file size and subsequently using less server bandwidth. So here's the PHP code:- function minify($_src) { // Buffer output ob_start(); $_time=microtime(TRUE); $_ptr=0; while ($_ptr<=strlen($_src)) { if ($_src[$_ptr]=='/') { // Let's presume it's a regex pattern $_regex=TRUE; if ($_ptr>0) { // Backtrack and va...
2 comments
Read more

Combined Pre-order and Post-order Non-recursive DOM Tree Traversal Algorithm

After a lot of googling around, I discovered that a lot of sites discuss pre-order, in-order and post-order algorithms focused on binary trees. Most of the code are familiar textbook materials. Only a few take up more complicated tree structures like DOM documents. Both recursive and iterative approaches to tree traversal have their pros and cons. And I'm not here to overemphasize any of these. Instead we'll take a different approach that's as fast, if not better than any other. The algorithm presented here is written in PHP and allows you to combine both pre-order and post-order traversal sequence in a single pass/loop. We'll be needing a stack that will contain all the nodes we passed along the way as we go through each branch. The traditional method of iterative traversal using a "visited" flag attached to each node has a 1:1 correspondence to the total number of nodes. On the other hand, the use of a stack is proportional to the height (or depth) of th...
Post a Comment
Read more