Javascript-ONLY DOM Tree Traversal - DFS and BFS?

Question

Can anyone provide either code, pseudocode, or even provide good links to implementing DFS (Depth-first search) and BFS (breadth-first search) in plain JavaScript (No JQuery, or any helper libraries)? I've been trying to understand how to implement either traversal, but I can't seem to really distinguish the difference of a BFS and DFS implementation.

If we want a concrete problem as an example: I want to traverse down the DOM at a given node, and get all the class names.

(The only way I can think to traverse is to go through each parent node, get what I need from that node which in this example is the class name, then see if they have children, recurse for each child. I believe this is DFS? Again, I'm having a hard time understanding the differences in a DOM traversal implementation!)

Finally, sorry if this is a repeat. I've searched everywhere for good, clear examples but haven't found any great answers! If there's already a good answer out there, please let me know :)

Answer 1

Let's use the following HTML code as an example:

<div class="a">
    <div class="aa">
        <span class="aaa">
        </span>
        <span class="aab">
        </span>
    </div>
    <div class="ab">
        <span class="aba">
        </span>
        <span class="abb">
        </span>
    </div>
</div>

DFS will always go to the next level of nodes first, and only if there are no more un-traversed child nodes will it step to a next node on the current level.

A DFS would traverse the nodes of the example in the following order:

a, aa, aaa, aab, ab, aba, abb

BFS will always traverse all the nodes in the current level first and only after that will it go to the next level of nodes.

A BFS would traverse the nodes of the example in the following order:

a, aa, ab, aaa, aab, aba, abb

There isn't a definite answer which one of these you should use. Usually it depends on your needs.

Implementation details:

For a DFS people often use a stack.

Pseudo code:

stack my_stack;
list visited_nodes;
my_stack.push(starting_node);

while my_stack.length > 0
   current_node = my_stack.pop();

   if current_node == null
       continue;
   if current_node in visited_nodes
      continue;
   visited_nodes.add(current_node);

   // visit node, get the class or whatever you need

   foreach child in current_node.children
      my_stack.push(child);

This code will go until there is any nodes in the stack. In each step we get the top node in the stack and if it's not null and if we haven't visited it before than we visit it and add all its children to the stack.

Queue is usually used for the BFS.

Pseudo code:

queue my_queue;
list visited_nodes;
my_queue.enqueue(starting_node);

while my_queue.length > 0
   current_node = my_queue.dequeue();

   if current_node == null
       continue;
   if current_node in visited_nodes
      continue;
   visited_nodes.add(current_node);

   // visit node, get the class or whatever you need

   foreach child in current_node.children
      my_queue.enqueue(child);

This code will go until there is any nodes in the queue. In each step we get the first node in the queue and if it's not null and if we haven't visited it before than we visit it and add all its children to the queue.

Note that the main difference between the two algorithm is the data type we use.

Answer 2

DFS:

function m(elem) {
    elem.childNodes.forEach(function(a) {
        m(a);
    });
    //do sth with elem
}
m(document.body);

This loops through all elements, and for each element through each child's and so on.

BFS:

var childs = [];

function m(elem) {
    elem.childNodes.forEach(function(a) {
        childs.push(a);
    });
    b = childs;
    childs = [];
    b.forEach(function(a) {
        m(a);
    });
}
m(document.body);

This loops through the elements, pushes their children onto a stack, and starts again with each of them. As you can see, this consumes much more space (the child's array) which is not the best...

Answer 3

For DFS you can use the TreeWalker or NodeIterator API and filter with NodeFilter.SHOW_ELEMENT.