Non-recursive Preorder Traversal - Part 1

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

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  2    3      6     
      7    8    9     
     
      10     
     
11     
     
      12       
      
       13         ...14       
      
15       
      
       16       
      
17     
     
18     ...19   20           
             
     
    
     
    
     
      
      
               ...      
      
      
      
      
      
    
     
    ...  

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.

Traverse/walk DOM tree recursively

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:

1.

function findNodeByTag(startNode, tagName) {

2.

    if (startNode.nodeName.toLowerCase() == tagName.toLowerCase()) return startNode;

3.

    var childList = startNode.childNodes;

4.

    for (var i=0; i<childList.length; i++) {

5.

        return findNodeByTag(childList[i], tagName);

6.

    }

7.

    return null;

8.

}

And you call it:

1.

findNodeByTag(myDOMobj, "img");