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 5 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 at 21:54

answered Jul 9 at 21:11

basilikum
1662

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

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

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

Nicely done. You don't need a stack because you have a pointer to the parent node. It illustrates how much easier to read a recursive algorithm is though! – FizzyTea Jul 9 at 21:47

1

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

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 at 9:50

Xotic750 · Answer 3 · 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	4 months ago
viewed	220 times
active	4 months ago

Implementing an algorithm that walks the DOM without recursion

migrated from stackoverflow.com Jul 9 at 20:42

3 Answers

Your Answer

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

Implementing an algorithm that walks the DOM without recursion

migrated from stackoverflow.com Jul 9 at 20:42

3 Answers

Your Answer

Sign up or login

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