Non-recursive Preorder Traversal - Part 3

Non-recursive preorder

All recursive functions can be unrolled to normal loops. It is not as elegant but it is much faster than recursion as there will only be a single function call.

Non-recursive preorder traversals usually requires that you keep track of multiple state variables to distinguise which nodes have already been visited. It can get quite complicated and hard to understand.

A DOM tree however is more simple as it provides all the nessesary node references out of the box.

Each node in a DOM tree have the following references

• node.parentNode
• node.previousSibling
• node.nextSibling
• node.firstChild
• node.lastChild
• node.childNodes - a collection (think of it as an array) of references to all child nodes

Taking advantage of the sibling references an algorithm for a non-recursive preorder traversal can be constructed as

 1 function preorderTraversal(root) {
 2   var n = root;
 3   while(n) {
 4     // If node have already been visited
 5     if (n.v) {
 6       // Remove mark for visited nodes
 7       n.v = false;
 8       // Once we reach the root element again traversal
 9       // is done and we can break
10       if (n == root)
11         break;
12       if (n.nextSibling)
13         n = n.nextSibling;
14       else
15         n = n.parentNode;
16     }
17     // else this is the first visit to the node
18     else {
19       //
20       // Do something with node here...
21       //
22       // If node has childnodes then we mark this node as
23       // visited as we are sure to be back later
24       if (n.firstChild) {
25         n.v = true;
26         n = n.firstChild;
27       }
28       else if (n.nextSibling)
29         n = n.nextSibling;
30       else
31         n = n.parentNode;
32     }
33   }
34 }
function preorderTraversal(root) {
  var n = root;
  while(n) {
    // If node have already been visited
    if (n.v) {
      // Remove mark for visited nodes
      n.v = false;
      // Once we reach the root element again traversal
      // is done and we can break
      if (n == root)
        break;
      if (n.nextSibling)
        n = n.nextSibling;
      else
        n = n.parentNode;
    }
    // else this is the first visit to the node
    else {
      //
      // Do something with node here...
      //
      // If node has childnodes then we mark this node as
      // visited as we are sure to be back later
      if (n.firstChild) {
        n.v = true;
        n = n.firstChild;
      }
      else if (n.nextSibling)
        n = n.nextSibling;
      else
        n = n.parentNode;
    }
  }
}

In simple words the algorithm does the following

1. Start from root node
2. If node has not been visited go to 6.
3. If node is the root node terminate loop.
4. If node has a next sibling let node be that sibling. Go to 2.
5. If node has a parent node let node be that parent. Go to 2.
6. If node has child nodes mark node as visited and let node be the first child node. Go to 2.
7. If node has a next sibling let node be that sibling. Go to 2.
8. If node has a parent node let node be that parent. Go to 2.

As you can see it is a rather simple algorithm - and it is fast. The nodes are visited in the following order

All leaves are visited once while all branching nodes are visited twice. The red numbers are the steps where the node have already been visited and the variable v is true. When the number is red the node is just visted but not processed.

Note that the root element does not have to be the HTML element but can be any element in the document.

Leave a comment