Breadth First DOM Search Algorithm

Today I ran an experiment to compare the native JavaScript getElementsByTagName and YUIs getElementsByClassName on the document against a breadth first search of the document. My assumptions were that when searching for a single tag and/or class the first two methods would be substantially faster, and that breadth first was the right way to search, because the DOM is usually not as deep as it is wide. My hypothesis, however was that I could do more complex operations, such as finding multiple tags or multiple classes faster using the breadth first search.

Improving a manual DOM search is useful, because I wrote a module that manages tabs inside of a form. Normally, setting the tabIndex will work just fine, but when dynamically loading content into a form, it is easy to confuse the browser. The tab management module cares about 3 tag types: input, select, and textarea. Now one could do three getElementsByTagName and combine the results, but the elements wont necessarily be in the order that they appear in the DOM, which is important when tabbing. Instead, I manually iterate through the form DOM, so that I get the elements in the right order.

Unfortunately, this is a slow process, and I was hoping to improve it. However, since every node in the tree (below a given form node) needs to be searched, the breadth first search does not improve performance much. Anyway, here is the algorithm:

Example 1: Breadth First Search Algorithm

Core.Widget.BreadthFirstSearch = function(root, matchFx) {
    if (! (root)) {alert(Missing parameter in Core.Widget.BreadthFirstSearch.);}

    var mFx = matchFx || function() {return true;},
        queue = [],
        results = [],
        i = 0,
        n = 0;

    /**
     * Recursively searches the DOM, creating the queue.
     * @method recursiveFx
     * @param param {Element} Required. The parent node to examine.
     * @private
     */
    var recursiveFx = function(parent) {
        // ensure that the parent has children
        if (parent.childNodes.length) {
            var children = Array.get(parent.childNodes);
            queue = queue.concat(children);
            children.batch(recursiveFx);
        }

        // criteria matched for result queue
        if (mFx(queue[n])) {
            results[i] = queue[n];
            i += 1;
        }

        n += 1;
    };

    // start recursion
    recursiveFx(root);
    
    return results;
};

Simply pass in a DOM node and the algorithm will return an array of all its children. If you provide a match function, then the algorithm will only return an array of matching results. I threw together a simple test page to compare a few different searches of the document. Each time you run one of the tests, a p tag is added to the DOM making the DOM tree large, so the more you run tests, the longer each search takes. Unfortunately, my hypothesis was proven wrong and even the complex 3 tag search was out performed by simply concatenating the native JavaScript getElementsByTagName quickly outperforms the breadth first search.