Build tree array from flat array in javascript
There is an efficient solution if you use a map-lookup. If the parents always come before their children you can merge the two for-loops. It supports multiple roots. It gives an error on dangling branches, but can be modified to ignore them. It doesn't require a 3rd-party library. It's, as far as I can tell, the fastest solution.
function list_to_tree(list) { var map = {}, node, roots = [], i; for (i = 0; i < list.length; i += 1) { map[list[i].id] = i; // initialize the map list[i].children = []; // initialize the children } for (i = 0; i < list.length; i += 1) { node = list[i]; if (node.parentId !== "0") { // if you have dangling branches check that map[node.parentId] exists list[map[node.parentId]].children.push(node); } else { roots.push(node); } } return roots;}var entries = [{ "id": "12", "parentId": "0", "text": "Man", "level": "1", "children": null }, { "id": "6", "parentId": "12", "text": "Boy", "level": "2", "children": null }, { "id": "7", "parentId": "12", "text": "Other", "level": "2", "children": null }, { "id": "9", "parentId": "0", "text": "Woman", "level": "1", "children": null }, { "id": "11", "parentId": "9", "text": "Girl", "level": "2", "children": null }];console.log(list_to_tree(entries));If you're into complexity theory this solution is Θ(n log(n)). The recursive-filter solution is Θ(n^2) which can be a problem for large data sets.
( BONUS1 : NODES MAY or MAY NOT BE ORDERED )
( BONUS2 : NO 3RD PARTY LIBRARY NEEDED, PLAIN JS )
( BONUS3 : User "Elias Rabl" says this is the most performant solution, see his answer below )
Here it is:
const createDataTree = dataset => { const hashTable = Object.create(null); dataset.forEach(aData => hashTable[aData.ID] = {...aData, childNodes: []}); const dataTree = []; dataset.forEach(aData => { if(aData.parentID) hashTable[aData.parentID].childNodes.push(hashTable[aData.ID]) else dataTree.push(hashTable[aData.ID]) }); return dataTree;};Here is a test, it might help you to understand how the solution works :
it('creates a correct shape of dataTree', () => { const dataSet = [{ "ID": 1, "Phone": "(403) 125-2552", "City": "Coevorden", "Name": "Grady" }, { "ID": 2, "parentID": 1, "Phone": "(979) 486-1932", "City": "Chełm", "Name": "Scarlet" }]; const expectedDataTree = [{ "ID": 1, "Phone": "(403) 125-2552", "City": "Coevorden", "Name": "Grady", childNodes: [{ "ID": 2, "parentID": 1, "Phone": "(979) 486-1932", "City": "Chełm", "Name": "Scarlet", childNodes : [] }] }]; expect(createDataTree(dataSet)).toEqual(expectedDataTree);});
As mentioned by @Sander, @Halcyon`s answer assumes a pre-sorted array, the following does not. (It does however assume you have loaded underscore.js - though it could be written in vanilla javascript):
Code
// Example usagevar arr = [ {'id':1 ,'parentid' : 0}, {'id':2 ,'parentid' : 1}, {'id':3 ,'parentid' : 1}, {'id':4 ,'parentid' : 2}, {'id':5 ,'parentid' : 0}, {'id':6 ,'parentid' : 0}, {'id':7 ,'parentid' : 4}];unflatten = function( array, parent, tree ){ tree = typeof tree !== 'undefined' ? tree : []; parent = typeof parent !== 'undefined' ? parent : { id: 0 }; var children = _.filter( array, function(child){ return child.parentid == parent.id; }); if( !_.isEmpty( children ) ){ if( parent.id == 0 ){ tree = children; }else{ parent['children'] = children } _.each( children, function( child ){ unflatten( array, child ) } ); } return tree;}tree = unflatten( arr );document.body.innerHTML = "<pre>" + (JSON.stringify(tree, null, " "))<script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.9.1/underscore-min.js"></script>Requirements
It assumes the properties 'id' and 'parentid' indicate ID and parent ID respectively. There must be elements with parent ID 0, otherwise you get an empty array back. Orphaned elements and their descendants are 'lost'