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!

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