Depth First Search vs Breadth First Search

Question

So after years of teaching myself, I think I'm ready to stand on the shoulders of giants and ask you a good question!

I have a tree of nodes. What I want is a function that returns an array of the entire tree sorted by depth.

In my original attempt I wasn't aware at the time that I was performing a depth first search.

My solution was to:

• recursively walk the tree, annotating depth as I go along.
• sort the above based on the depth annotation.
• filter out the depth annotation and return the sorted array.

That was three steps invoking 3 loops! So then someone alerted me to the concept of a breadth first search. I did my research and built (on my own) a BFS function! It looked so simple and did what I needed.

Then when I timed both versions; completely bafflingly; the cumbersome DFS version is faster! Why???

Here is my depth-first-search:

function dfsElementsInTree(input){
 // perform depth first search but
 // return a depth sorted array of an element or elements and any children
 let output = [];
 if (Symbol.iterator in input)
 // input is a HTMLcollection
 for (const element of input)
 doTraversal(element);
 else
 doTraversal(input);
 
 return output.sort((a, b) => a.depth - b.depth).map(item=>item.element);
 function doTraversal(element, depth=0) {
 output.push({element, depth});
 if (element.children.length) depth++;
 for (const child of element.children)
 doTraversal(child, depth);
 }
}

Here is my breadth-first-search:

function bfsElementsInTree(input) {
 // perform a breadth first search in order to have elements ordered by depth.
 let output = [];
 let queue = [];
 let visited = [];
 const enqueue = item => {queue.push(item); visited.push(item);};
 if (Symbol.iterator in input)
 // input is a HTMLcollection
 for (const element of input)
 queue.push(element);
 else
 queue.push(input);
 
 while (queue.length) {
 for (const element of queue)
 for (const child of element.children)
 if (!visited.includes(child))
 enqueue(child);
 output.push(queue.shift());
 }
 
 return output;
}

---

Ready for benchmarking here: https://jsben.ch/ZNuAx

---

But if you want to test it yourself, here's some code to generate some trees:

// Create trees of divs as such:
// (left to right)
// 1
// 1 -> 2
// 1 -> 2 -> 3
// 1 -> 2
// 1
const a1 = document.createElement('div');
const a2 = document.createElement('div');
const a3 = document.createElement('div');
const a4 = document.createElement('div');
const a5 = document.createElement('div');
[a1,a2,a3,a4,a5].forEach(e => e.className ='1');
const b2 = document.createElement('div');
const b3 = document.createElement('div');
const b4 = document.createElement('div');
[b2,b3,b4].forEach(e => e.className ='2');
const c3 = document.createElement('div');
c3.className = '3';
a2.appendChild(b2);
b3.appendChild(c3);
a3.appendChild(b3);
a4.appendChild(b4);
[a1,a2,a3,a4,a5].forEach(e => document.body.appendChild(e));

Thank you so much for your time. It's a real treat to have an expert looking over my shoulder!

• vnp: Maintaining visited only makes sense for a generic graph (where you may visit a node from many other nodes). For a tree, it is a pure waste of time and space.
• aName: Right, that's what I thought, but if you comment it out, you get this (44) [div.1, div.1, div.1, div.1, div.1, div.2, div.2, div.2, div.3, div.2, div.2, div.2, div.3, div.3, div.2, div.2, div.3, div.3, div.3, div.2, div.3, div.3, div.3, div.3, div.3, div.3, div.3, div.3, div.3, div.3, div.3, div.3, div.3, div.3, div.3, div.3, div.3, div.3, div.3, div.3, div.3, div.3, div.3, div.3] which is crazy
• aName: Ah, I figured it out! The while AND the for loop together are excessive. Here is the new benchmark: jsben.ch/WBHuB

Answer 1

I solved it. It turns out my looping logic was a bit out. No need for both a while and a for! (and while we're at it, we don't have to check for visited. Thanks @vnp in comments)

edit: since I'm not actually using a queue, I missed that I don't now need to maintain two arrays! Thanks @Ry in the comments!)

Wrote it again for speed and here it is:

 function bfsElementsInTree(input) {
 // perform a breadth first search in order to have elements ordered by depth. (Deepest last)
 let output = [];
 if (Symbol.iterator in input)
 // input is a HTMLcollection
 for (let i = 0, max = input.length; i < max; i++)
 output[i] = input[i];
 else
 output.push(input);
 for (let i = 0; i < output.length; i++) {
 const children = output[i].children;
 for (let j = 0, max = children.length; j < max; j++)
 output.push(children[j]);
 }
 return output;
 }

And new benchmark: https://jsben.ch/F1zzW

• Ry-: Isn’t the queue the same as the output here? So you could return queue directly and remove output for more performance and memory wins.
• aName: You were right! Good catch!