12
\$\begingroup\$

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?

\$\endgroup\$

migrated from stackoverflow.com Jul 9 '13 at 20:42

This question came from our site for professional and enthusiast programmers.

8
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ This is very nice... there's just one fly in the ointment for practical use: in the acceptNode method (method of NodeFilter interface, it seems) there appears to be no easy way of getting the depth of the node passed as the parameter. Shame - non-recursive tree traversal is usually preferable because of memory questions, etc. \$\endgroup\$ – mike rodent Sep 16 '17 at 15:49
5
\$\begingroup\$

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.
\$\endgroup\$
  • 2
    \$\begingroup\$ Can you explain why your alternative version is better than the original version? \$\endgroup\$ – Hosch250 Jul 24 '15 at 0:26
  • 1
    \$\begingroup\$ Ooh, clever. I hadn't thought of this as a DFS problem. You deserve more upvotes! \$\endgroup\$ – o11c Jul 24 '15 at 1:35
  • \$\begingroup\$ I do wonder if it's possible to do the append-all-reversed in a better way. I'm not nearly familiar enough with javascript to know. \$\endgroup\$ – o11c Jul 24 '15 at 1:42
  • \$\begingroup\$ @Hosch250 which original version are you referring to? The one with recursion? The original poster was asking for a concise solution without recursion: that's what I was going for. \$\endgroup\$ – Andrew Jul 25 '15 at 1:00
  • \$\begingroup\$ @o11c I don't know about a better way, but some may find this easier to read: for (var i = node.childNodes.length-1; i >= 0; i--) { stack.push(node.childNodes[i]); } \$\endgroup\$ – Andrew Jul 25 '15 at 1:09
2
\$\begingroup\$

Here is another version that uses rather than . 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.