# Depth First Search vs Breadth First Search

Posted on

Problem

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);
}
}
``````

``````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!

Solution

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