Depth First Search vs Breadth First Search
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 &lt; max; i++)
        output[i] = input[i];
    else
      output.push(input);

    for (let i = 0; i &lt; output.length; i++) {
      const children = output[i].children;
      for (let j = 0, max = children.length; j &lt; max; j++)
        output.push(children[j]);
    }

    return output;
  }


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