JavaScript Lab - Articles - Non-recursive Preorder Traversal

Non-recursive Preorder Traversal - Part 2

Published on 1st of November 2008. Copyright Tavs Dokkedahl. Displayed 1781 time(s)

Recursive preorder

The easiest way to do a preorder traversal is by recursion. Starting from the root element the steps are

Handle node
For each child node recurse

To find all text nodes using a recursive approach one could write

 1 // HTML element
 2 var root = document.documentElement;
 3 recursivePreorder(root);
 4 // Recusively find and handle all text nodes
 5 function recursivePreorder(node) {
 6   // If node is a text node
 7   if (node.type == 3) {
 8     // Do something with node
 9   }
10   // else recurse for each child node
11   else {
12     for(var i=0; i<node.childNodes.length; i++)
13       recursivePreorder(node.childNodes[i]);
14   }
15 }
// HTML element
var root = document.documentElement;
recursivePreorder(root);
// Recusively find and handle all text nodes
function recursivePreorder(node) {
  // If node is a text node
  if (node.type == 3) {
    // Do something with node
  }
  // else recurse for each child node
  else {
    for(var i=0; i<node.childNodes.length; i++)
      recursivePreorder(node.childNodes[i]);
  }
}

This will iterate over all nodes in the document visiting each node in the document exactly one time.

Unless you have nested elements thousands of levels deep the above code is very unlikely to cause a stack overflow. The maximum number of function calls at any one time is limited to the height of the tree - not the number of elements.

Recursion is elegant and easy to read but it is also slow. If we are searching a document with 1000 nodes we are calling the recursivePreorder 1000 times.

If you are only concerned with traversing element nodes - nodes which are tags - in a document then you should use the following instead

 1 // Get all elements
 2 var elms = document.getElementsByTagName('*');
 3 var l = elms.length;
 4 // For each node
 5 for(var i=0; i<l; i++) {
 6   // Do something with node
 7   alert(elms[i].tagName);
 8 }
// Get all elements
var elms = document.getElementsByTagName('*');
var l = elms.length;
// For each node
for(var i=0; i<l; i++) {
  // Do something with node
  alert(elms[i].tagName);
}

The method document.getElementsByTagName returns a collection of all element nodes in the document when passing '*' as an argument.

Even better they come preordered. This is faster than anything else you can do but this method does not pick up the text nodes in the document.

Tweaking the for loop to look for text nodes is not a simple task although it may seem that way. I will leave that challenge to you and if you come up with something fancy (and fast) then don't hesitate to leave a comment.

« Part 1

Part 3 »

Non-recursive Preorder Traversal - Part 2

Recursive preorder

Leave a comment