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!
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\$(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\$