JavaScript Lab Articles Nonrecursive Preorder Traversal Part 1

A brief introduction to trees

If you have never heard of trees keep reading otherwise you can safely skip to the next section.

A tree is a datastructure which organizes data as shown on the picture below.

The root is the top most element. A root element has no parent element nor any siblings.

A branch has exactly 1 parent element and at least 1 child element. It may have 0 or more siblings.

A leaf has exactly 1 parent and no child elements. If may have 0 or more siblings.

In general all elements in the tree are called nodes and we differentiate between root, branches and leafs by checking their parent/child properties.

The DOM of a HTML document is such a tree. Below is a picture of how some of the elements of this page are ordered.

This tree corresponds to the following HTML code

1 <html> 2 <head> 3 <title> 4 JavaScript Lab - Articles - Non-recursive Preorder Traversal 5 </title> 6 <meta name=\"language\" content=\"EN\" /> 7 </head> 8 <body> 9 <div id=\"header\"> 10 </div> 11 <div id=\"toolbar\"> 12 <ul> 13 ... 14 </ul> 15 <div class=\"clear\"> 16 </div> 17 </div> 18 ... 19 </body> 20 </html>

<html>
  <head>
    <title>
      JavaScript Lab - Articles - Non-recursive Preorder Traversal
    </title>
    <meta name=\"language\" content=\"EN\" />
  </head>
  <body>
    <div id=\"header\">
    </div>
    <div id=\"toolbar\">
      <ul>
        ...
      </ul>
      <div class=\"clear\">
      </div>
    </div>
    ...
  </body>
</html>

The root node is the html element. It has 2 children - the head and the body elements.

The head element has 2 children - the title and the meta elements. These two elements are siblings and share the same parent node.

The meta element is a leaf as it has no child nodes whereas the title is not as it has a string value.

The title string itself is a text node and a leaf.

When we are doing a preorder traversal we are visiting each node in the tree in the following order

So a preorder traversal is a ordering of the elements as they are ordered in the source code.

Task definition: You have a DOM tree (startNode which can be the whole document), and need to find first specific tag in this tree.

Here is the recursion function to do this:

function findNodeByTag(startNode, tagName) {
    if (startNode.nodeName.toLowerCase() == tagName.toLowerCase()) return startNode;
    var childList = startNode.childNodes;
    for (var i=0; i<childList.length; i++) {
        return findNodeByTag(childList[i], tagName);
    }
    return null;
}

And you call it:

1.findNodeByTag(myDOMobj, "img");

JavaScript Lab Articles Nonrecursive Preorder Traversal Part 1

Non-recursive Preorder Traversal - Part 1

A brief introduction to trees

Traverse/walk DOM tree recursively