Efficiently "joining" a large nested array (i.e. tree) of strings into a single string

Question

I have an array that looks like this (but can be very big, and with longer strings):

var treeOfStrings = [
  'abc',
  'def',
  [
    'ghij',
    [
      'k',
      'l'
    ],
    'mnop'
  ],
  'qrst',
  'uv',
  'wxyz'
];

I want to turn it into a single string, but since it is big and this is in a performance sensitive place, I'd like to do it in a very efficient way.

The current approach (below) is to first make a single array (by recursively walking the children and using push() on a single output array), and then doing a join()....but it seems like there could be a more efficient way, since this one is pretty heavy on the usage of push() so it could do lots of little allocations.

function treeJoin(tree) {
  var out = [];
  flattenArray(tree);
  return out.join('');

  function flattenArray(branch) {
    var len = branch.length;
    var item;
    for(var i=0; i<len; i++) {
      item = branch[i];
      if(typeof item === "string")
        out.push(item);
      else
        flattenArray(item);
    }
  }
}

(the solution will need to work in all reasonably modern browsers as well as node.js)

Edit:

I timed these functions, and interestingly, the simplest way of doing it (well, simplest to me) is actually the fastest (see below). I would have thought doing "+=" on a string over and over was slow, but nope, it's screaming fast (in Chrome). Over ten times faster than the method below that uses map() and join(), and about 6 times faster than the method that overrides Array.toString(), and twice as fast as my method that flattens the tree into a single array and then uses a single join(). Crazy.

treeJoin = function (tree) {
  var s = ''
  var len = tree.length;
  var item;
  for(var i=0; i<len; i++) {
    item = tree[i];
    if(item.push)
      s += treeJoin(item);
    else
      s += item;
  }
  return s
}

Answer 1

Sometimes cheating works:

var result = treeOfStrings.toString().replace(/,/g,"");

Converting arrays to strings joins their elements with commas, then strip out the commas and you're good to go.

Doesn't behave quite as hoped if any of the pieces already contained commas.

Answer 2

You could do it a little more concisely (though it'd be algorithmically the same) with .map() and .join():

var flatTree = tree.map(function flattener(elem) {
  return (typeof elem) === "string" ? elem : elem.map(flattener).join("");
}).join("");

That'll work if the "tree" is just strings and sub-arrays.

Answer 3

Join is not recursive

var str=treeOfStrings.join("");
console.log(str); //"abc,def,ghij,k,l,mnop,qrst,uv,wxyz"

So @Pointy's method uses map to do a recursive join.

toString on an array will make a call to join instead, which will use join's default delimiter, a comma. (See here for reference)

For the nested arrays, it will automatically join recursively, even if you override toString:

Array.prototype.toString=function() {
return this.join("");
};

then

var str=treeOfStrings.toString(); 
console.log(str); //"abcdefghijklmnopqrstuvwxyz"

Since the toString is done recursively to the nested array elements, so is the join. JS handles the recursion for you, so I would assume it is a fast algorithm, but I haven't benchmarked.

Overriding toString may not be desirable in all situations, but it is just another option.