Make a tree from a flat data structure

makeTree.js

'use strict';

const { deepEqual } = require('assert');

/**
 * Sample data structure.
 *
 * The items are roughly sorted already, with the top-level item as the root of
 * the tree.
 *
 * @const {Object[]}
 */
const data = [{
  _id: 1,
  _parentId: null,
}, {
  _id: 2,
  _parentId: 1,
}, {
  _id: 3,
  _parentId: 1,
}, {
  _id: 4,
  _parentId: 2,
}, {
  _id: 5,
  _parentId: 2,
}, {
  _id: 6,
  _parentId: 2,
}, {
  _id: 7,
  _parentId: 3,
}, {
  _id: 8,
  _parentId: 3,
}, {
  _id: 9,
  _parentId: 6,
}, {
  _id: 10,
  _parentId: 6,
}, {
  _id: 11,
  _parentId: 8,
}];

/**
 * Make a tree from a flat structure.
 *
 * @todo This passes all `items` down recursively. Improve performance by only
 * passing down needed items, cutting down on `Array#reduce` loops.
 *
 * @param {Object[]} items Expected to be pre-sorted, with the parent as the
 * first item.
 * @param {Object} [parentItem]
 * @returns {Object}
 */
function makeTree(items, parentItem) {
  const localParentItem = parentItem ? parentItem : items[0];
  const _children = items.reduce((memo, item) => {
    return item._parentId === localParentItem._id ?
      memo.concat(makeTree(items, item)) :
      memo;
  }, []);

  return _children.length ?
    Object.assign({}, localParentItem, { _children }) :
    localParentItem;
}

const actual = makeTree(data);
const expected = {
  _id: 1,
  _parentId: null,
  _children: [{
    _id: 2,
    _parentId: 1,
    _children: [{
      _id: 4,
      _parentId: 2,
    }, {
      _id: 5,
      _parentId: 2,
    }, {
      _id: 6,
      _parentId: 2,
      _children: [{
        _id: 9,
        _parentId: 6,
      }, {
        _id: 10,
        _parentId: 6,
      }]
    }],
  }, {
    _id: 3,
    _parentId: 1,
    _children: [{
      _id: 7,
      _parentId: 3,
    }, {
      _id: 8,
      _parentId: 3,
      _children: [{
        _id: 11,
        _parentId: 8,
      }],
    }],
  }],
}

try {
  deepEqual(actual, expected);
  console.log('makeTree works!');
} catch (error) {
  console.error(error);
}