Skip to main content

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 the tallest branch.

To determine how we handle each node in the tree, we need some indicator/flag to tell us whether we're traversing downward/right or ascending from the end of a branch (a leaf).

Without much ado:-


public function traverse($tree) {
 $_stack=array();
 $_flag=FALSE;
 $_node=$tree->documentElement;
 while ($_node) {
  if (!$_flag) {
   // insert pre-order code here
   if ($_node->firstChild) {
    array_push($_stack,$_node);
    $_flag=FALSE;
    $_node=$_node->firstChild;
    continue;
   }
  }
  // insert post-order code here
  $_flag=FALSE;
  $_node=$_node->nextSibling;
  if (!$_node && !empty($_stack)) {
   $_node=array_pop($_stack);
   $_flag=TRUE;
  }
 }
}

The traversal strategy is no different from other algorithms, except the way we use our stack and the $_flag indicator (which is really a state indicator and vector).

  1. Initialize stack. Start with a descending vector because we're not traversing the tree at this point from bottom-up.
  2. If not ascending from a child node, save each node in the stack as we pass along the way to the deepest part of the left-most branch.
  3. Once we reach a leaf, we go to the leaf's sibling and repeat step 2.
  4. If there are no more siblings, we pop the stack (effectively going up to the parent node) and repeat step 2.

Where indicated in the code snippet, you can insert both pre-order and post-order processing routines in the loop. This is more efficient than having to traverse a tree twice to do both. But first you need a situation where you'll be needing both. Now we can talk about that at a later time.

You might also want to take a look at the stackless approach here.

Comments

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 validate …

PHP Fat-Free Framework - Less Hype, More Meat

Too often we see code hyped up as "frameworks". But when it comes to applying them to real-world situations, they fall short and sloppy or at the other end of the scale - are huge beasts that behave like control freaks - which make them unusable or hostile to average programmers.

Some are touted as frameworks yet they act simply as front-end controllers which do nothing more than route URLs to classes, functions or include files. They make programming a bit easier, but lacking in many MVC aspects. Some require a fixed directory structure - an open invitation to hackers. Other procedural frameworks use method chaining (which can be quite long), you'd wonder at times what the right sequence should be. Some are just too bloated with so many features than you'll ever need to use in simple blog or wiki applications.

Most frameworks brag about being "lightweight" - which seems to be a relative term. Does a 50MByte framework that consumes a lot of resou…