30 Days of Algorithms : Day 05 - Create a tree from a flat array.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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