Non-recursive Preorder Traversal - Part 3

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

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

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 }

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

Tree data structure

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.

« Part 2 Part 4 » 

Leave a comment


Email (if you want a response)

Comment (no HTML)

Spam challenge
Sorry to bother you but spam is a royal pain, so please answer this simple question to verify that you are in fact human(oid)

Question: "What is the name of the programming language which this website is about?"