Implementing an algorithm that walks the DOM without recursion

Question

Here's a simple algorithm that walks the DOM given a node:

function walkDOM(n) {
    do {
        console.log(n);
        if (n.hasChildNodes()) {
            walkDOM(n.firstChild)
        }
    } while (n = n.nextSibling)
}

I wanted to implement it iteratively as an exercise, and came up with this:

function walkDOM2(n) {
    var recStack = [];
    // First get the parent of the given node, so that
    // you can get the siblings of the given node too
    // (starting from the last sibling),
    // rather than just start with the children of the
    // given node.
    // (This is to make this behave the
    // same way as the recursive one.)
    recStack.push(n.parentNode);

    while (recStack.length > 0) {
        var current = recStack.pop();
        // Log only if the current node is
        // the given node or a node below it.
        // (This is to make this behave the
        // same way as the recursive one.)
        if (current != n.parentNode)
            console.log(current);
        if (!current.hasChildNodes())
            continue;

        current = current.lastChild;
        do {
            recStack.push(current);
            // Skip the sibling nodes
            // before the given node.
            // (This is to make this behave the
            // same way as the recursive one.)
            if (current === n)
                break;
        } while (current = current && current.previousSibling);
    }
}

I have used a couple tricks to make it behave the same way as the first recursive version. Is there a more concise way of writing this without recursion?

Answer 1

I know you are doing this as an exercise, and personally I like the recursive function. But just as an alternative, there is also the much forgotten TreeWalker API.

Browser compatibility

Supported by IE9+, FF2+, Chrome 1+, Safari 3+, Opera 9+

Javascript

var treeWalker = document.createTreeWalker(document.getElementById("list"), NodeFilter.SHOW_ALL, {
    acceptNode: function (node) {
        return NodeFilter.FILTER_ACCEPT;
    }
}, false);

do {
    console.log(treeWalker.currentNode);
} while (treeWalker.nextNode());

On jsfiddle

Answer 2

Here is a solution that is about as concise as your recursive solution. (8 lines of code.)

  function walkDOM2(n) {
    var stack = [n];
    while (stack.length > 0) {
      var node = stack.pop();
      console.log(node);
      stack = stack.concat(Array.prototype.slice.call(node.childNodes, 0).reverse());
    }
  }

Some notes on the above:

• After you pop an item off the end of the stack, you replace it with it's children.
• The children are reversed so that the first child is placed at the end of the stack, so it will be the next node to be popped.
• Use Array.prototype.slice.call() to turn the childNodes NodeList into an Array so it can be added to the stack with concat.
• There is no hasChildNodes() check, but sometimes there will be no child nodes and an empty array will be added to the stack.

Answer 3

Here is another version that uses iteration rather than recursion. It uses continue, break, and a label.

Avoid using labels

Labels are not very commonly used in JavaScript since they make programs harder to read and understand. As much as possible, avoid using labels and, depending on the cases, prefer calling functions or throwing an error.

Javascript

function walkDOM(root, func) {
    var node = root;

    start: while (node) {
        func(node);
        if (node.firstChild) {
            node = node.firstChild;
            continue start;
        }

        while (node) {
            if (node === root) {
                break start;
            }

            if (node.nextSibling) {
                node = node.nextSibling;
                continue start;
            }

            node = node.parentNode;
        }
    }
}

walkDOM(document.body, function (node) {
    console.log(node);
});

On jsfiddle

Finally, here is a jsperf of the Recursive vs Iterative methods.