1
\$\begingroup\$

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!

\$\endgroup\$
3
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – vnp
    Apr 23, 2020 at 20:31
  • \$\begingroup\$ 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 \$\endgroup\$
    – aName
    Apr 24, 2020 at 8:28
  • \$\begingroup\$ Ah, I figured it out! The while AND the for loop together are excessive. Here is the new benchmark: jsben.ch/WBHuB \$\endgroup\$
    – aName
    Apr 24, 2020 at 8:42

1 Answer 1

1
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Ry-
    Apr 24, 2020 at 10:30
  • \$\begingroup\$ You were right! Good catch! \$\endgroup\$
    – aName
    Apr 24, 2020 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.