1) преобразуете массив в объект с помощью _.indexBy из lodash/underscore при этом так как внутри массива объекты, то полученый объект будет содержать ссылки на те же объекты
2) пробегаем исходный массив и отмечаем в childs у родителя
UPD: писал с телефона в дороге, дополню кодом
Простой вариант, как описано мною выше:
var catsIndex = _.indexBy(cats, 'id');
cats.forEach(function(el) {
if(!catsIndex[el.parent_id]) return;
if(!catsIndex[el.parent_id].childs) catsIndex[el.parent_id].childs = [];
catsIndex[el.parent_id].childs.push(el.id);
});
console.log(cats);
Оптимизированный вариант, в один проход:
var catsChilds = {};
for(var i = cats.length; i--;) {
if(catsChilds[cats[i].id]) {
cats[i].childs = catsChilds[cats[i].id];
} else {
cats[i].childs = catsChilds[cats[i].id] = [];
}
if(!catsChilds[cats[i].parent_id]) {
catsChilds[cats[i].parent_id] = [];
}
catsChilds[cats[i].parent_id].push(cats[i].id);
}
console.log(cats);
P.S. если нужно именно новый массив, не затрагивая исходный, то перед выполнением кода нужно сделать deapClone и работать уже с клоном, реализацию deapClone можете легко нагуглить