[Alexandroppolus]

1) Предполагаем, что чилд может появиться в массиве раньше своего парента
2) Дерево состоит из тех же объектов, которые лежат в массиве, некоторые из них модифицируются. Если надо делать копию, то в строке 5 заменить arr[i] на создание копии arr[i]

function createTree(arr) {
  if (!arr || !arr.length) { return []; }
  var tree = [], map = new Map();
  for (var i = 0, len = arr.length; i < len; ++i) {
    var item = arr[i];
    var mapItem = map.get(item.id);
    if (!mapItem || Array.isArray(mapItem)) {
      if (mapItem) {
        item.children = mapItem;
      }
      map.set(item.id, item);
    }
    if (item.parentId == null) {
      tree.push(item);
    } else {
      var parentItem = map.get(item.parentId);
      if (!parentItem) {
        map.set(item.parentId, [item]);
      } else {
        var children = Array.isArray(parentItem) ?
          parentItem :
          (parentItem.children = parentItem.children || []);
        children.push(item);
      }
    }
  }
  return tree;
}