p1xel p1xel - 24 days ago 9
Javascript Question

DOM Tree Walker as an exercise[JS]

Write a function called nextNode that can be used to walk through all the nodes of a DOM tree. The function should take a node as an argument, and return the next node in the tree. For example, the following loop would visit every node once, and only once:

var node = document.body;
do {
node = nextNode(node);
} while (node != null)


I think from DOM it's supposed to only use
firstChild, lastChild, previousSibling, nextSibling,
and
parentNode
.

Code below should be how i imagine it to work. The problem is with the childNodes, seems like it needs a for/while loop to work. But the loop needs to somehow remember the last childNodes position and add i+1 because of it's call in do/while loop. I don't know what condition to give there and i get infinite loops.

nextNode = function(node) {
// for/while loop?
if (node.childNodes) {
}
else if (node.nextSibling) {
node = node.nextSibling;
}
else {
node = node.parentNode.nextSibling;
}
return node;
};


Unless i'm completely wrong about it. Could someone elaborate or point me in the right direction?

Answer

You could use this function:

var nextNode = function(node, deeperDone) {
  return !node ? undefined
       : node.childNodes.length && !deeperDone ? node.childNodes[0]
       : node.nextSibling ? node.nextSibling
       : nextNode(node.parentNode, 1);
};

It uses recursion for backtracking through the parents, since the next node may be several levels up the hierarchy.

Here is a demo:

var nextNode = function(node, deeperDone) {
  return !node ? undefined
       : node.childNodes.length && !deeperDone ? node.childNodes[0]
       : node.nextSibling ? node.nextSibling
       : nextNode(node.parentNode, 1);
};

for (var node = document.getElementById('a'); node; node = nextNode(node)) {
    if (node.id) console.log(node.id); // skip text nodes
}
<div id="a">
   <div id="b"></div>
   <div id="c">
       <div id="d"></div>
   </div>
   <div id="e">
       <div id="f">
            <div id="g"></div>
            <div id="h"></div>
            <div id="i"></div>
       </div>
       <div id="j">
            <div id="k"></div>
            <div id="l"></div>
       </div>
   </div>
   <div id="m"></div>
</div>

Although you asked for a function taking a node as argument, there is the TreeWalker object (which Orial referred to), which is a kind of cursor, on which you can call the nextNode method repeatedly to walk through nodes in this order. Note that at the start, before moving to the next, you'd want to do something with the root node as well, which you can (at the start) also access with the currentNode property:

var walker = document.createTreeWalker(document.getElementById('a'), 
                                       NodeFilter.SHOW_ELEMENT);
do {
    console.log(walker.currentNode.id); 
} while (walker.nextNode());
<div id="a">
   <div id="b"></div>
   <div id="c">
       <div id="d"></div>
   </div>
   <div id="e">
       <div id="f">
            <div id="g"></div>
            <div id="h"></div>
            <div id="i"></div>
       </div>
       <div id="j">
            <div id="k"></div>
            <div id="l"></div>
       </div>
   </div>
   <div id="m"></div>
</div>