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?

basilikum · Accepted Answer · 2013-07-09 21:54:58Z

up vote 8 down vote accepted

How about something like this?

function iterate() {
    var ch = document.body;
    while (ch) {
        //if node has children, get the first child
        if (ch.children.length > 0) {
            ch = ch.firstElementChild;

        //if node has silbing, get the sibling
        } else if (ch.nextElementSibling) {
            ch = ch.nextElementSibling;

        //if it has neither, crawl up the dom until you find a node that has a sibling and get that sibling
        } else {
            do {
                ch = ch.parentNode;
                //if we are back at document.body, return!
                if (ch === document.body) {
                    return;
                }
            } while (!ch.nextElementSibling)
            ch = ch.nextElementSibling;
        }
        console.log(ch.id);
    }
}

iterate();

FIDDLE

edited Jul 9 '13 at 21:54

answered Jul 9 '13 at 21:11

basilikum

21114

Just took a quick look at it, looks much better than my version. – hattenn Jul 9 '13 at 21:25

sorry, just realized that is doesn't work properly yet, will update my answer. – basilikum Jul 9 '13 at 21:27

ok, just updated it. It needed the continue, otherwise it would print out the same nodes multiple times. – basilikum Jul 9 '13 at 21:32

1

walkDOM and walkDOM2 visit TextNodes whereas iterate does not; at least in my browser. – abuzittin gillifirca Jul 11 '13 at 7:16

1

@abuzittingillifirca you're right, it does only iterate over element nodes. If you want text nodes as well as all kinds of other nodes, you would have slightly modify this script and change for instance nextElementSibling to nextSibling and firstElementChild to firstChild. – basilikum Jul 11 '13 at 7:40

| show 4 more comments

Xotic750 · Answer 2 · 2013-07-14 00:02:12Z

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

Thank you for the answer, I wasn't aware of this one. – hattenn Jul 14 '13 at 9:50 — hattenn, Jul 14 '13 at 9:50

Andrew · Answer 3 · 2015-07-25 01:01:55Z

up vote 4 down vote

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.

edited Jul 25 '15 at 1:01

answered Jul 24 '15 at 0:13

Andrew

412

2

Can you explain why your alternative version is better than the original version? – Hosch250 Jul 24 '15 at 0:26

1

Ooh, clever. I hadn't thought of this as a DFS problem. You deserve more upvotes! – o11c Jul 24 '15 at 1:35

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. – o11c Jul 24 '15 at 1:42

@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. – Andrew Jul 25 '15 at 1:00

@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]); } – Andrew Jul 25 '15 at 1:09

add a comment |

Xotic750 · Answer 4 · 2013-07-14 23:52:26Z

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.

asked	3 years ago
viewed	3234 times
active	1 year ago

current community

your communities

more stack exchange communities

Implementing an algorithm that walks the DOM without recursion

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

4 Answers 4

Your Answer

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

Hot Network Questions

current community

your communities

more stack exchange communities

Implementing an algorithm that walks the DOM without recursion

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

4 Answers 4

Did you find this question interesting? Try our newsletter

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions