Create an array of arrays from a flat array in javascript

Question

I have a complex json file that I have to process with javascript to make it hierarchical in order to build a tree later. Each json entry has: id: a unique identifier, parentId: id of the parent node (which is 0 if the node is the root of the tree) level: depth level in the tree

Json data is already "ordered". I mean that the record will have a parent node or a node brother above it, and below it a child node or node brother.

Entrance:

{ "People": [ { "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 } ], "Animals": [ { "id": "5", "parentId": "0", "text": "Dog", "level": "1", "children": null }, { "id": "8", "parentId": "5", "text": "Puppy", "level": "2", "children": null }, { "id": "10", "parentId": "13", "text": "Cat", "level": "1", "children": null }, { "id": "14", "parentId": "13", "text": "Kitten", "level": "2", "children": null }, ] } 

Expected Result:

 { "People": [ { "id": "12", "parentId": "0", "text": "Man", "level": "1", "children": [ { "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": { "id": "11", "parentId": "9", "text": "Girl", "level": "2", "children": null } } ], "Animals": [ { "id": "5", "parentId": "0", "text": "Dog", "level": "1", "children": { "id": "8", "parentId": "5", "text": "Puppy", "level": "2", "children": null } }, { "id": "10", "parentId": "13", "text": "Cat", "level": "1", "children": { "id": "14", "parentId": "13", "text": "Kitten", "level": "2", "children": null } } ] } 

Answer 1

There is an effective solution if you use map search. If parents always come in front of their children, you can combine the two loops. It supports multiple roots. It gives an error on dangling branches, but can be modified to ignore them. This does not require a third-party library. This, as far as I can tell, is the quickest 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" }, { /*...*/ } ]; console.log(list_to_tree(entries)); 

If you are involved in complexity theory, this is the solution Θ (n log (n)). A recursive filter is Θ (n ^ 2), which can be a problem for large data sets.

Answer 2

As @Sander mentioned, @Halcyon's answer assumes a pre-sorted array, and the next one doesn't. (However, it is assumed that you downloaded underscore.js - although it can be written in vanilla javascript):

The code

 // Example usage var 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

The id and parentid properties are assumed to indicate the identifier and parent identifier, respectively. There must be elements with parent identifier 0, otherwise you will get an empty array. Orphaned elements and their descendants are "lost"

http://jsfiddle.net/LkkwH/1/

Answer 3

There was the same problem, but I could not be sure that the data was sorted or not . I could not use a third-party library, so this is just vanilla Js; Input can be taken from @Stephen;

  var arr = [ {'id':1 ,'parentid' : 0}, {'id':4 ,'parentid' : 2}, {'id':3 ,'parentid' : 1}, {'id':5 ,'parentid' : 0}, {'id':6 ,'parentid' : 0}, {'id':2 ,'parentid' : 1}, {'id':7 ,'parentid' : 4}, {'id':8 ,'parentid' : 1} ]; function unflatten(arr) { var tree = [], mappedArr = {}, arrElem, mappedElem; // First map the nodes of the array to an object -> create a hash table. for(var i = 0, len = arr.length; i < len; i++) { arrElem = arr[i]; mappedArr[arrElem.id] = arrElem; mappedArr[arrElem.id]['children'] = []; } for (var id in mappedArr) { if (mappedArr.hasOwnProperty(id)) { mappedElem = mappedArr[id]; // If the element is not at the root level, add it to its parent array of children. if (mappedElem.parentid) { mappedArr[mappedElem['parentid']]['children'].push(mappedElem); } // If the element is at the root level, add it to first level elements array. else { tree.push(mappedElem); } } } return tree; } var tree = unflatten(arr); document.body.innerHTML = "<pre>" + (JSON.stringify(tree, null, " ")) 

Js feed

Flat array to tree

Answer 4

A very easy way to do it.

(BONUS1: NODES MAY or MAY NOT BE ORDERED)

(BONUS2: THIRD PARTY LIBRARY NOT REQUIRED, SIMPLY JS)

(BONUS3: Elias Rabl user says this is the fastest solution, see his answer below)

 const createDataTree = dataset => { let hashTable = Object.create(null) dataset.forEach( aData => hashTable[aData.ID] = { ...aData, childNodes : [] } ) let 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 can help you understand how the solution works:

 it('creates a correct shape of dataTree', () => { let dataSet = [ { "ID": 1, "Phone": "[phone]", "City": "Coevorden", "Name": "Grady" }, { "ID": 2, "parentID": 1, "Phone": "[phone]", "City": "Chełm", "Name": "Scarlet" } ] let expectedDataTree = [ { "ID": 1, "Phone": "[phone]", "City": "Coevorden", "Name": "Grady", childNodes : [ { "ID": 2, "parentID": 1, "Phone": "[phone]", "City": "Chełm", "Name": "Scarlet", childNodes : [] } ] } ] expect( createDataTree(dataSet) ).toEqual(expectedDataTree) }); 

Answer 5

simpler list-to-tree-lite function

npm install list-to-tree-lite

listToTree(list)

source:

 function listToTree(data, options) { options = options || {}; var ID_KEY = options.idKey || 'id'; var PARENT_KEY = options.parentKey || 'parent'; var CHILDREN_KEY = options.childrenKey || 'children'; var tree = [], childrenOf = {}; var item, id, parentId; for (var i = 0, length = data.length; i < length; i++) { item = data[i]; id = item[ID_KEY]; parentId = item[PARENT_KEY] || 0; // every item may have children childrenOf[id] = childrenOf[id] || []; // init its children item[CHILDREN_KEY] = childrenOf[id]; if (parentId != 0) { // init its parent children object childrenOf[parentId] = childrenOf[parentId] || []; // push it into its parent children object childrenOf[parentId].push(item); } else { tree.push(item); } }; return tree; } 

jsfiddle

Answer 6

Use this ES6 approach. It works like a charm

 // Data Set // One top level comment var comments = [{ id: 1, parent_id: null }, { id: 2, parent_id: 1 }, { id: 3, parent_id: 1 }, { id: 4, parent_id: 2 }, { id: 5, parent_id: 4 }]; const nest = (items, id = null, link = 'parent_id') => items .filter(item => item[link] === id) .map(item => ({ ...item, children: nest(items, item.id) })); nest(comments); 

Answer 7

You can handle this issue with two-line coding:

 _(flatArray).forEach(f=> {f.nodes=_(flatArray).filter(g=>g.parentId==f.id).value();}); var resultArray=_(flatArray).filter(f=>f.parentId==null).value(); 

Test online (see Browser Console for the created tree)

Requirements:

1- Install lodash 4 (Javascript library for managing objects and collections using executing methods => like Linq in C #) Lodash

2- FlatArray as below:

  var flatArray= [{ id:1,parentId:null,text:"parent1",nodes:[] } ,{ id:2,parentId:null,text:"parent2",nodes:[] } , { id:3,parentId:1,text:"childId3Parent1",nodes:[] } , { id:4,parentId:1,text:"childId4Parent1",nodes:[] } , { id:5,parentId:2,text:"childId5Parent2",nodes:[] } , { id:6,parentId:2,text:"childId6Parent2",nodes:[] } , { id:7,parentId:3,text:"childId7Parent3",nodes:[] } , { id:8,parentId:5,text:"childId8Parent5",nodes:[] }]; 

I thank Mr. Bakhshabadi

Good luck

Answer 8

This may be a useful list-to-tree package. Install:

 bower install list-to-tree --save 

or

 npm install list-to-tree --save 

For example, there is a list:

 var list = [ { id: 1, parent: 0 }, { id: 2, parent: 1 }, { id: 3, parent: 1 }, { id: 4, parent: 2 }, { id: 5, parent: 2 }, { id: 6, parent: 0 }, { id: 7, parent: 0 }, { id: 8, parent: 7 }, { id: 9, parent: 8 }, { id: 10, parent: 0 } ]; 

Use package list for tree:

 var ltt = new LTT(list, { key_id: 'id', key_parent: 'parent' }); var tree = ltt.GetTree(); 

Result:

 [{ "id": 1, "parent": 0, "child": [ { "id": 2, "parent": 1, "child": [ { "id": 4, "parent": 2 }, { "id": 5, "parent": 2 } ] }, { "id": 3, "parent": 1 } ] }, { "id": 6, "parent": 0 }, { "id": 7, "parent": 0, "child": [ { "id": 8, "parent": 7, "child": [ { "id": 9, "parent": 8 } ] } ] }, { "id": 10, "parent": 0 }]; 

Answer 9

This offer is for disordered items. This function works with one loop and hash table and collects all elements with their id . If the root node is found, the object is added to the result array.

 function getTree(data, root) { var o = {}; data.forEach(function (a) { if (o[a.id] && o[a.id].children) { a.children = o[a.id].children; } o[a.id] = a; o[a.parentId] = o[a.parentId] || {}; o[a.parentId].children = o[a.parentId].children || []; o[a.parentId].children.push(a); }); return o[root].children; } var data = { People: [{ 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 }], Animals: [{ id: "5", parentId: "0", text: "Dog", level: "1", children: null }, { id: "8", parentId: "5", text: "Puppy", level: "2", children: null }, { id: "10", parentId: "13", text: "Cat", level: "1", children: null }, { id: "14", parentId: "13", text: "Kitten", level: "2", children: null }] }, tree = Object.keys(data).reduce(function (r, k) { r[k] = getTree(data[k], '0'); return r; }, {}); console.log(tree); 

 .as-console-wrapper { max-height: 100% !important; top: 0; } 

Answer 10

I wrote a test script to evaluate the performance of the two most common solutions (this means that the input data should not be sorted in advance and the code does not depend on third-party libraries), proposed by users of shekhardtu ( see answer ) and FurkanO ( see answer ).

http://playcode.io/316025?tabs=console&script.js&output

FurkanO's solution seems to be the fastest.

Answer 11

Here's a simple helper function that I created after the above answers, adapted to the Babel environment:

 import { isEmpty } from 'lodash' export default function unflattenEntities(entities, parent = {id: null}, tree = []) { let children = entities.filter( entity => entity.parent_id == parent.id) if (!isEmpty( children )) { if ( parent.id == null ) { tree = children } else { parent['children'] = children } children.map( child => unflattenEntities( entities, child ) ) } return tree } 

Answer 12

also do this with lodashjs (v4.x)

 function buildTree(arr){ var a=_.keyBy(arr, 'id') return _ .chain(arr) .groupBy('parentId') .forEach(function(v,k){ k!='0' && (a[k].children=(a[k].children||[]).concat(v)); }) .result('0') .value(); } 

Answer 13

I like @WilliamLeung's pure JavaScript solution, but sometimes you need to make changes to an existing array in order to maintain an object reference.

 function listToTree(data, options) { options = options || {}; var ID_KEY = options.idKey || 'id'; var PARENT_KEY = options.parentKey || 'parent'; var CHILDREN_KEY = options.childrenKey || 'children'; var item, id, parentId; var map = {}; for(var i = 0; i < data.length; i++ ) { // make cache if(data[i][ID_KEY]){ map[data[i][ID_KEY]] = data[i]; data[i][CHILDREN_KEY] = []; } } for (var i = 0; i < data.length; i++) { if(data[i][PARENT_KEY]) { // is a child if(map[data[i][PARENT_KEY]]) // for dirty data { map[data[i][PARENT_KEY]][CHILDREN_KEY].push(data[i]); // add child to parent data.splice( i, 1 ); // remove from root i--; // iterator correction } else { data[i][PARENT_KEY] = 0; // clean dirty data } } }; return data; } 

Exapmle: https://jsfiddle.net/kqw1qsf0/17/

Answer 14

 var data = [{"country":"india","gender":"male","type":"lower","class":"X"}, {"country":"china","gender":"female","type":"upper"}, {"country":"india","gender":"female","type":"lower"}, {"country":"india","gender":"female","type":"upper"}]; var seq = ["country","type","gender","class"]; var treeData = createHieArr(data,seq); console.log(treeData) function createHieArr(data,seq){ var hieObj = createHieobj(data,seq,0), hieArr = convertToHieArr(hieObj,"Top Level"); return [{"name": "Top Level", "parent": "null", "children" : hieArr}] function convertToHieArr(eachObj,parent){ var arr = []; for(var i in eachObj){ arr.push({"name":i,"parent":parent,"children":convertToHieArr(eachObj[i],i)}) } return arr; } function createHieobj(data,seq,ind){ var s = seq[ind]; if(s == undefined){ return []; } var childObj = {}; for(var ele of data){ if(ele[s] != undefined){ if(childObj[ele[s]] == undefined){ childObj[ele[s]] = []; } childObj[ele[s]].push(ele); } } ind = ind+1; for(var ch in childObj){ childObj[ch] = createHieobj(childObj[ch],seq,ind) } return childObj; } } 

Answer 15

You might take a look at the npm package tree utility. It can also be very convenient if you want to load data from an SQL DB data table. You can also easily add additional data to nodes in the created tree.

Disclaimer, I made this package.

Answer 16

You can use this "treeify" package from Github here or NPM .

Mounting:

$ npm install --save-dev treeify-js

Answer 17

Here is a modified version of Stephen Harris, which is a simple ES5, and returns an object with a key to an identifier, and does not return an array of nodes at both the top level and the child ones.

 unflattenToObject = function(array, parent) { var tree = {}; parent = typeof parent !== 'undefined' ? parent : {id: 0}; var childrenArray = array.filter(function(child) { return child.parentid == parent.id; }); if (childrenArray.length > 0) { var childrenObject = {}; // Transform children into a hash/object keyed on token childrenArray.forEach(function(child) { childrenObject[child.id] = child; }); if (parent.id == 0) { tree = childrenObject; } else { parent['children'] = childrenObject; } childrenArray.forEach(function(child) { unflattenToObject(array, child); }) } return tree; }; var 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} ]; tree = unflattenToObject(arr); 

Answer 18

This is the modified version above that works with several root elements, I use the GUID for my identifiers and parent elements, so in the user interface that creates them, I hardcode the root elements to about 0000000-00000-00000-TREE-ROOT -item

var tree = unflatten (records, "TREE-ROOT-ITEM");

 function unflatten(records, rootCategoryId, parent, tree){ if(!_.isArray(tree)){ tree = []; _.each(records, function(rec){ if(rec.parentId.indexOf(rootCategoryId)>=0){ // change this line to compare a root id //if(rec.parentId == 0 || rec.parentId == null){ // example for 0 or null var tmp = angular.copy(rec); tmp.children = _.filter(records, function(r){ return r.parentId == tmp.id; }); tree.push(tmp); //console.log(tree); _.each(tmp.children, function(child){ return unflatten(records, rootCategoryId, child, tree); }); } }); } else{ if(parent){ parent.children = _.filter(records, function(r){ return r.parentId == parent.id; }); _.each(parent.children, function(child){ return unflatten(records, rootCategoryId, child, tree); }); } } return tree; } 

Answer 19

Copied from the Internet http://jsfiddle.net/stywell/k9x2a3g6/

  function list2tree(data, opt) { opt = opt || {}; var KEY_ID = opt.key_id || 'ID'; var KEY_PARENT = opt.key_parent || 'FatherID'; var KEY_CHILD = opt.key_child || 'children'; var EMPTY_CHILDREN = opt.empty_children; var ROOT_ID = opt.root_id || 0; var MAP = opt.map || {}; function getNode(id) { var node = [] for (var i = 0; i < data.length; i++) { if (data[i][KEY_PARENT] == id) { for (var k in MAP) { data[i][k] = data[i][MAP[k]]; } if (getNode(data[i][KEY_ID]) !== undefined) { data[i][KEY_CHILD] = getNode(data[i][KEY_ID]); } else { if (EMPTY_CHILDREN === null) { data[i][KEY_CHILD] = null; } else if (JSON.stringify(EMPTY_CHILDREN) === '[]') { data[i][KEY_CHILD] = []; } } node.push(data[i]); } } if (node.length == 0) { return; } else { return node; } } return getNode(ROOT_ID) } var opt = { "key_id": "ID", //节点的ID "key_parent": "FatherID", //节点的父级ID "key_child": "children", //子节点的名称"empty_children": [], //子节点为空时,填充的值 //这个参数为空时,没有子元素的元素不带key_child属性;还可以为null或者[],同理"root_id": 0, //根节点的父级ID "map": { //在节点内映射一些值 //对象的键是节点的新属性; 对象的值是节点的老属性,会赋值给新属性"value": "ID", "label": "TypeName", } }; 

Answer 20

You can use the npm array package for the tree https://github.com/alferov/array-to-tree . It converts a simple array of nodes (with pointers to parent nodes) into a nested data structure.

Solves the problem of converting the data sets extracted from the database into a nested data structure (i.e. navigation tree).

Using:

 var arrayToTree = require('array-to-tree'); var dataOne = [ { id: 1, name: 'Portfolio', parent_id: undefined }, { id: 2, name: 'Web Development', parent_id: 1 }, { id: 3, name: 'Recent Works', parent_id: 2 }, { id: 4, name: 'About Me', parent_id: undefined } ]; arrayToTree(dataOne); /* * Output: * * Portfolio * Web Development * Recent Works * About Me */ 

Answer 21

This is an old branch, but I thought the update would never hurt, with ES6 you can do:

 (parent => categories.filter(cat => cat. parentId === parent).map(cat=>({...cat, children: recursive1(cat.id)})))(0) 

hope this helps someone

Answer 22

this is what i used in a jet project

 // ListToTree.js import _filter from 'lodash/filter'; import _map from 'lodash/map'; export default (arr, parentIdKey) => _map(_filter(arr, ar => !ar[parentIdKey]), ar => ({ ...ar, children: _filter(arr, { [parentIdKey]: ar.id }), })); 

using:

 // somewhere.js import ListToTree from '../Transforms/ListToTree'; const arr = [ { "id":"Bci6XhCLZKPXZMUztm1R", "name":"Sith" }, { "id":"C3D71CMmASiR6FfDPlEy", "name":"Luke", "parentCategoryId":"ltatOlEkHdVPf49ACCMc" }, { "id":"aS8Ag1BQqxkO6iWBFnsf", "name":"Obi Wan", "parentCategoryId":"ltatOlEkHdVPf49ACCMc" }, { "id":"ltatOlEkHdVPf49ACCMc", "name":"Jedi" }, { "id":"pw3CNdNhnbuxhPar6nOP", "name":"Palpatine", "parentCategoryId":"Bci6XhCLZKPXZMUztm1R" } ]; const response = ListToTree(arr, 'parentCategoryId'); 

exit:

 [ { "id":"Bci6XhCLZKPXZMUztm1R", "name":"Sith", "children":[ { "id":"pw3CNdNhnbuxhPar6nOP", "name":"Palpatine", "parentCategoryId":"Bci6XhCLZKPXZMUztm1R" } ] }, { "id":"ltatOlEkHdVPf49ACCMc", "name":"Jedi", "children":[ { "id":"C3D71CMmASiR6FfDPlEy", "name":"Luke", "parentCategoryId":"ltatOlEkHdVPf49ACCMc" }, { "id":"aS8Ag1BQqxkO6iWBFnsf", "name":"Obi Wan", "parentCategoryId":"ltatOlEkHdVPf49ACCMc" } ] } ]''' 

Answer 23

1. without third-party library
2. no need to pre-order the array
3. You can get any part of the tree you want

Try this

 function getUnflatten(arr,parentid){ let output = [] for(const obj of arr){ if(obj.parentid == parentid) let children = getUnflatten(arr,obj.id) if(children.length){ obj.children = children } output.push(obj) } } return output } 

Check it out on Jsfiddle