30 Days of Algorithms : Day 05 - Create a tree from a flat array.
/** | |
* Converts a flat array to a tree with runtime O(n) | |
* | |
* Big-O : O(n) | |
* | |
* This algorithm was taken from Phillip Stanislaus's "Performant Array to Tree" | |
* which has O(n) complexity. It builds the tree in a single pass. | |
* @link https://github.com/philipstanislaus | |
* @link https://www.npmjs.com/package/performant-array-to-tree | |
* @see https://github.com/iconifyit/30-Days-of-Algorithms | |
*/ | |
const arrayToTree = (items) => { | |
/** | |
* The nested tree. | |
* @type {*[]} | |
*/ | |
const rootItems = []; | |
/** | |
* Stores all already processed items with their ids as | |
* key so we can easily look them up | |
* @type {{}} | |
*/ | |
const lookup = {}; | |
/* ================================================================== | |
* Idea of this loop: | |
* ================================================================== | |
* Whenever an item has a parent, but the parent is not yet in the | |
* lookup object, we store a preliminary parent in the lookup object | |
* and fill it with the data of the parent later if an item has no | |
* parentId, add it as a root element to rootItems | |
*/ | |
for (const item of items) { | |
const itemId = item['id'] | |
const parentId = item['parentId'] | |
/* | |
* Check whether item already exists in the lookup table. If not, | |
* add a placeholder. We'll add the details later. | |
*/ | |
if (! lookup[itemId]) lookup[itemId] = { ['children']: [] } | |
/* | |
* Fill in the details of our previously-created placeholder | |
* in the lookup table. | |
*/ | |
lookup[itemId] = { ...item, ['children']: lookup[itemId]['children'] } | |
/* | |
* Create a symbol for our item. | |
*/ | |
const TreeItem = lookup[itemId] | |
/* ================================================================== | |
* Determine where the item goes in the tree. | |
* ================================================================== */ | |
/* | |
* If the item has no parentId, it is the root node. | |
*/ | |
if (parentId === null || parentId === undefined || parentId === '') { | |
rootItems.push(TreeItem) | |
} | |
/* | |
* If the item has a parentId, add it to the tree. | |
*/ | |
else { | |
/* | |
* Check whether the parent already exists in the lookup table. | |
* If not, add a placeholder. We'll add the details later. | |
*/ | |
if (! lookup[parentId]) lookup[parentId] = { ['children']: [] } | |
/* | |
* Add the current item to the parent | |
*/ | |
lookup[parentId]['children'].push(TreeItem) | |
} | |
} | |
return rootItems | |
} | |
const tree = arrayToTree([ | |
{ id: 'x001', parentId: null, name: 'Joe' }, | |
{ id: 'x002', parentId: 'x001', name: 'Sammy', children : []}, | |
{ id: 'x003', parentId: 'x001', name: 'Emily', children : []}, | |
{ id: 'x004', parentId: 'x001', name: 'Scott', children : []}, | |
{ id: 'x005', parentId: 'x002', name: 'Fred', children : []}, | |
{ id: 'x006', parentId: 'x002', name: 'Vickie', children : []}, | |
{ id: 'x007', parentId: 'x002', name: 'Marlow', children : []}, | |
{ id: 'x008', parentId: 'x003', name: 'Anna', children : []}, | |
{ id: 'x009', parentId: 'x003', name: 'Brad', children : []}, | |
{ id: 'x010', parentId: 'x003', name: 'Sarah', children : []}, | |
{ id: 'x011', parentId: 'x004', name: 'Mark', children : []}, | |
{ id: 'x012', parentId: 'x004', name: 'Debbie', children : []}, | |
{ id: 'x013', parentId: 'x004', name: 'Boomer', children : []}, | |
{ id: 'x014', parentId: 'x005', name: 'Stuey', children : []}, | |
{ id: 'x015', parentId: 'x005', name: 'Jessie', children : []}, | |
{ id: 'x016', parentId: 'x005', name: 'Tolstoy', children : []}, | |
{ id: 'x017', parentId: 'x009', name: 'Maddie', children : []}, | |
{ id: 'x018', parentId: 'x009', name: 'Scout', children : []}, | |
{ id: 'x019', parentId: 'x009', name: 'Jordie', children : []}, | |
]); | |
console.log("\nTree:\n") | |
console.log( | |
"Tree: \n" + | |
JSON.stringify(tree, undefined, 2) | |
) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment