Skip to content

Instantly share code, notes, and snippets.

@swashcap swashcap/makeTree.js
Last active Nov 1, 2016

Embed
What would you like to do?
Make a tree from a flat data structure
'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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.