I have a complex json file that I have to handle with javascript to make it hierarchical, in order to later build a tree. Every entry of the json has : id : a unique id, parentId : the id of the parent node (which is 0 if the node is a root of the tree) level : the level of depth in the tree
The json data is already "ordered". I mean that an entry will have above itself a parent node or brother node, and under itself a child node or a brother node.
Input :
{
"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 output :
{
"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
}
}
]
}
This question is related to
javascript
arrays
list
tree
ES6 function to convert an Array of nodes (related by parent ID) - to a Tree structure:
/**
* Convert nodes list related by parent ID - to tree.
* @syntax getTree(nodesArray [, rootID [, propertyName]])
*
* @param {Array} arr Array of nodes
* @param {integer} id Defaults to 0
* @param {string} p Property name. Defaults to "parent_id"
* @returns {Object} Nodes tree
*/
const getTree = (arr, p = "parent_id") => arr.reduce((o, n) => {
if (!o[n.id]) o[n.id] = {};
if (!o[n[p]]) o[n[p]] = {};
if (!o[n[p]].nodes) o[n[p]].nodes= [];
if (o[n.id].nodes) n.nodes= o[n.id].nodes;
o[n[p]].nodes.push(n);
o[n.id] = n;
return o;
}, {});
Having our Tree in place, here's a recursive function to build the UL > LI Elements:
/**
* Convert Tree structure to UL>LI and append to Element
* @syntax getTree(treeArray [, TargetElement [, onLICreatedCallback ]])
*
* @param {Array} tree Tree array of nodes
* @param {Element} el HTMLElement to insert into
* @param {function} cb Callback function called on every LI creation
*/
const treeToHTML = (tree, el, cb) => el.append(tree.reduce((ul, n) => {
const li = document.createElement('li');
if (cb) cb.call(li, n);
if (n.nodes?.length) treeToHTML(n.nodes, li, cb);
ul.append(li);
return ul;
}, document.createElement('ul')));
Here's an example having a linear Array of nodes and using both the above functions:
const getTree = (arr, p = "parent_id") => arr.reduce((o, n) => {_x000D_
if (!o[n.id]) o[n.id] = {};_x000D_
if (!o[n[p]]) o[n[p]] = {};_x000D_
if (!o[n[p]].nodes) o[n[p]].nodes = [];_x000D_
if (o[n.id].nodes) n.nodes = o[n.id].nodes;_x000D_
o[n[p]].nodes.push(n);_x000D_
o[n.id] = n;_x000D_
return o;_x000D_
}, {});_x000D_
_x000D_
_x000D_
const treeToHTML = (tree, el, cb) => el.append(tree.reduce((ul, n) => {_x000D_
const li = document.createElement('li');_x000D_
if (cb) cb.call(li, n);_x000D_
if (n.nodes?.length) treeToHTML(n.nodes, li, cb);_x000D_
ul.append(li);_x000D_
return ul;_x000D_
}, document.createElement('ul')));_x000D_
_x000D_
_x000D_
// DEMO TIME:_x000D_
_x000D_
const nodesList = [_x000D_
{id: 10, parent_id: 4, text: "Item 10"}, // PS: Order does not matters_x000D_
{id: 1, parent_id: 0, text: "Item 1"}, _x000D_
{id: 4, parent_id: 0, text: "Item 4"},_x000D_
{id: 3, parent_id: 5, text: "Item 3"},_x000D_
{id: 5, parent_id: 4, text: "Item 5"},_x000D_
{id: 2, parent_id: 1, text: "Item 2"},_x000D_
];_x000D_
const myTree = getTree(nodesList)[0].nodes; // Get nodes of Root (0)_x000D_
_x000D_
treeToHTML(myTree, document.querySelector("#tree"), function(node) {_x000D_
this.textContent = `(${node.parent_id} ${node.id}) ${node.text}`;_x000D_
this._node = node;_x000D_
this.addEventListener('click', clickHandler);_x000D_
});_x000D_
_x000D_
function clickHandler(ev) {_x000D_
if (ev.target !== this) return;_x000D_
console.clear();_x000D_
console.log(this._node.id);_x000D_
};
_x000D_
<div id="tree"></div>
_x000D_
I've written a test script to evaluate the performance of the two most general solutions (meaning that the input does not have to be sorted beforehand and that the code does not depend on third party libraries), proposed by users shekhardtu (see answer) and FurkanO (see answer).
http://playcode.io/316025?tabs=console&script.js&output
FurkanO's solution seems to be the fastest.
/*_x000D_
** performance test for https://stackoverflow.com/questions/18017869/build-tree-array-from-flat-array-in-javascript_x000D_
*/_x000D_
_x000D_
// Data Set (e.g. nested comments)_x000D_
var comments = [{_x000D_
id: 1,_x000D_
parent_id: null_x000D_
}, {_x000D_
id: 2,_x000D_
parent_id: 1_x000D_
}, {_x000D_
id: 3,_x000D_
parent_id: 4_x000D_
}, {_x000D_
id: 4,_x000D_
parent_id: null_x000D_
}, {_x000D_
id: 5,_x000D_
parent_id: 4_x000D_
}];_x000D_
_x000D_
// add some random entries_x000D_
let maxParentId = 10000;_x000D_
for (let i=6; i<=maxParentId; i++)_x000D_
{_x000D_
let randVal = Math.floor((Math.random() * maxParentId) + 1);_x000D_
comments.push({_x000D_
id: i,_x000D_
parent_id: (randVal % 200 === 0 ? null : randVal)_x000D_
});_x000D_
}_x000D_
_x000D_
// solution from user "shekhardtu" (https://stackoverflow.com/a/55241491/5135171)_x000D_
const nest = (items, id = null, link = 'parent_id') =>_x000D_
items_x000D_
.filter(item => item[link] === id)_x000D_
.map(item => ({ ...item, children: nest(items, item.id) }));_x000D_
;_x000D_
_x000D_
// solution from user "FurkanO" (https://stackoverflow.com/a/40732240/5135171)_x000D_
const createDataTree = dataset => {_x000D_
let hashTable = Object.create(null)_x000D_
dataset.forEach( aData => hashTable[aData.id] = { ...aData, children : [] } )_x000D_
let dataTree = []_x000D_
dataset.forEach( aData => {_x000D_
if( aData.parent_id ) hashTable[aData.parent_id].children.push(hashTable[aData.id])_x000D_
else dataTree.push(hashTable[aData.id])_x000D_
} )_x000D_
return dataTree_x000D_
};_x000D_
_x000D_
_x000D_
/*_x000D_
** lets evaluate the timing for both methods_x000D_
*/_x000D_
let t0 = performance.now();_x000D_
let createDataTreeResult = createDataTree(comments);_x000D_
let t1 = performance.now();_x000D_
console.log("Call to createDataTree took " + Math.floor(t1 - t0) + " milliseconds.");_x000D_
_x000D_
t0 = performance.now();_x000D_
let nestResult = nest(comments);_x000D_
t1 = performance.now();_x000D_
console.log("Call to nest took " + Math.floor(t1 - t0) + " milliseconds.");_x000D_
_x000D_
_x000D_
_x000D_
_x000D_
//console.log(nestResult);_x000D_
//console.log(createDataTreeResult);_x000D_
_x000D_
// bad, but simple way of comparing object equality_x000D_
console.log(JSON.stringify(nestResult)===JSON.stringify(createDataTreeResult));
_x000D_
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",
}
};
Here's a simple helper function that I created modeled after the above answers, tailored to a 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
}
Incase anyone needs it for multiple parent. Refer id 2 which has multiple parents
const dataSet = [{
"ID": 1,
"Phone": "(403) 125-2552",
"City": "Coevorden",
"Name": "Grady"
},
{"ID": 2,
"Phone": "(403) 125-2552",
"City": "Coevorden",
"Name": "Grady"
},
{
"ID": 3,
"parentID": [1,2],
"Phone": "(979) 486-1932",
"City": "Chelm",
"Name": "Scarlet"
}];
const expectedDataTree = [
{
"ID":1,
"Phone":"(403) 125-2552",
"City":"Coevorden",
"Name":"Grady",
"childNodes":[{
"ID":2,
"parentID":[1,3],
"Phone":"(979) 486-1932",
"City":"Chelm",
"Name":"Scarlet",
"childNodes":[]
}]
},
{
"ID":3,
"parentID":[],
"Phone":"(403) 125-2552",
"City":"Coevorden",
"Name":"Grady",
"childNodes":[
{
"ID":2,
"parentID":[1,3],
"Phone":"(979) 486-1932",
"City":"Chelm",
"Name":"Scarlet",
"childNodes":[]
}
]
}
];
const createDataTree = dataset => {
const hashTable = Object.create(null);
dataset.forEach(aData => hashTable[aData.ID] = {...aData, childNodes: []});
const dataTree = [];
dataset.forEach(Datae => {
if (Datae.parentID && Datae.parentID.length > 0) {
Datae.parentID.forEach( aData => {
hashTable[aData].childNodes.push(hashTable[Datae.ID])
});
}
else{
dataTree.push(hashTable[Datae.ID])
}
});
return dataTree;
};
window.alert(JSON.stringify(createDataTree(dataSet)));
_x000D_
also do it 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();
}
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):
// Example usage_x000D_
var arr = [_x000D_
{'id':1 ,'parentid' : 0},_x000D_
{'id':2 ,'parentid' : 1},_x000D_
{'id':3 ,'parentid' : 1},_x000D_
{'id':4 ,'parentid' : 2},_x000D_
{'id':5 ,'parentid' : 0},_x000D_
{'id':6 ,'parentid' : 0},_x000D_
{'id':7 ,'parentid' : 4}_x000D_
];_x000D_
_x000D_
unflatten = function( array, parent, tree ){_x000D_
tree = typeof tree !== 'undefined' ? tree : [];_x000D_
parent = typeof parent !== 'undefined' ? parent : { id: 0 };_x000D_
_x000D_
var children = _.filter( array, function(child){ return child.parentid == parent.id; });_x000D_
_x000D_
if( !_.isEmpty( children ) ){_x000D_
if( parent.id == 0 ){_x000D_
tree = children; _x000D_
}else{_x000D_
parent['children'] = children_x000D_
}_x000D_
_.each( children, function( child ){ unflatten( array, child ) } ); _x000D_
}_x000D_
_x000D_
return tree;_x000D_
}_x000D_
_x000D_
tree = unflatten( arr );_x000D_
document.body.innerHTML = "<pre>" + (JSON.stringify(tree, null, " "))
_x000D_
<script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.9.1/underscore-min.js"></script>
_x000D_
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'
Use this ES6 approach. Works like charm
// Data Set_x000D_
// One top level comment _x000D_
const comments = [{_x000D_
id: 1,_x000D_
parent_id: null_x000D_
}, {_x000D_
id: 2,_x000D_
parent_id: 1_x000D_
}, {_x000D_
id: 3,_x000D_
parent_id: 1_x000D_
}, {_x000D_
id: 4,_x000D_
parent_id: 2_x000D_
}, {_x000D_
id: 5,_x000D_
parent_id: 4_x000D_
}];_x000D_
_x000D_
const nest = (items, id = null, link = 'parent_id') =>_x000D_
items_x000D_
.filter(item => item[link] === id)_x000D_
.map(item => ({ ...item, children: nest(items, item.id) }));_x000D_
_x000D_
console.log(_x000D_
nest(comments)_x000D_
)
_x000D_
I like @WilliamLeung's pure JavaScript solution, but sometimes you need to make changes in existing array to keep a reference to object.
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/
I wrote an ES6 version based on @Halcyon answer
const array = [
{
id: '12',
parentId: '0',
text: 'one-1'
},
{
id: '6',
parentId: '12',
text: 'one-1-6'
},
{
id: '7',
parentId: '12',
text: 'one-1-7'
},
{
id: '9',
parentId: '0',
text: 'one-2'
},
{
id: '11',
parentId: '9',
text: 'one-2-11'
}
];
// Prevent changes to the original data
const arrayCopy = array.map(item => ({ ...item }));
const listToTree = list => {
const map = {};
const roots = [];
list.forEach((v, i) => {
map[v.id] = i;
list[i].children = [];
});
list.forEach(v => (v.parentId !== '0' ? list[map[v.parentId]].children.push(v) : roots.push(v)));
return roots;
};
console.log(listToTree(arrayCopy));
The principle of this algorithm is to use "map" to establish an index relationship. It is easy to find "item" in the list by "parentId", and add "children" to each "item", because "list" is a reference relationship, so "roots" will Build relationships with the entire tree.
Had the same problem, but I could not be certain that the data was sorted or not. I could not use a 3rd party library so this is just vanilla Js; Input data can be taken from @Stephen's example;
var arr = [_x000D_
{'id':1 ,'parentid' : 0},_x000D_
{'id':4 ,'parentid' : 2},_x000D_
{'id':3 ,'parentid' : 1},_x000D_
{'id':5 ,'parentid' : 0},_x000D_
{'id':6 ,'parentid' : 0},_x000D_
{'id':2 ,'parentid' : 1},_x000D_
{'id':7 ,'parentid' : 4},_x000D_
{'id':8 ,'parentid' : 1}_x000D_
];_x000D_
function unflatten(arr) {_x000D_
var tree = [],_x000D_
mappedArr = {},_x000D_
arrElem,_x000D_
mappedElem;_x000D_
_x000D_
// First map the nodes of the array to an object -> create a hash table._x000D_
for(var i = 0, len = arr.length; i < len; i++) {_x000D_
arrElem = arr[i];_x000D_
mappedArr[arrElem.id] = arrElem;_x000D_
mappedArr[arrElem.id]['children'] = [];_x000D_
}_x000D_
_x000D_
_x000D_
for (var id in mappedArr) {_x000D_
if (mappedArr.hasOwnProperty(id)) {_x000D_
mappedElem = mappedArr[id];_x000D_
// If the element is not at the root level, add it to its parent array of children._x000D_
if (mappedElem.parentid) {_x000D_
mappedArr[mappedElem['parentid']]['children'].push(mappedElem);_x000D_
}_x000D_
// If the element is at the root level, add it to first level elements array._x000D_
else {_x000D_
tree.push(mappedElem);_x000D_
}_x000D_
}_x000D_
}_x000D_
return tree;_x000D_
}_x000D_
_x000D_
var tree = unflatten(arr);_x000D_
document.body.innerHTML = "<pre>" + (JSON.stringify(tree, null, " "))
_x000D_
JS Fiddle
a more simple function list-to-tree-lite
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's children object
childrenOf[parentId] = childrenOf[parentId] || [];
// push it into its parent's children object
childrenOf[parentId].push(item);
} else {
tree.push(item);
}
};
return tree;
}
This is an old thread but I figured an update never hurts, with ES6 you can do:
const data = [{
id: 1,
parent_id: 0
}, {
id: 2,
parent_id: 1
}, {
id: 3,
parent_id: 1
}, {
id: 4,
parent_id: 2
}, {
id: 5,
parent_id: 4
}, {
id: 8,
parent_id: 7
}, {
id: 9,
parent_id: 8
}, {
id: 10,
parent_id: 9
}];
const arrayToTree = (items=[], id = null, link = 'parent_id') => items.filter(item => id==null ? !items.some(ele=>ele.id===item[link]) : item[link] === id ).map(item => ({ ...item, children: arrayToTree(items, item.id) }))
const temp1=arrayToTree(data)
console.log(temp1)
const treeToArray = (items=[], key = 'children') => items.reduce((acc, curr) => [...acc, ...treeToArray(curr[key])].map(({ [`${key}`]: child, ...ele }) => ele), items);
const temp2=treeToArray(temp1)
console.log(temp2)
_x000D_
hope it helps someone
You can handle this question with just 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 the browser console for created tree)
Requirements:
1- Install lodash 4 (a Javascript library for manipulating objects and collections with performant methods => like the Linq in c#) Lodash
2- A flatArray like 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:[]
}];
Thank Mr. Bakhshabadi
Good luck
var data = [{"country":"india","gender":"male","type":"lower","class":"X"},_x000D_
{"country":"china","gender":"female","type":"upper"},_x000D_
{"country":"india","gender":"female","type":"lower"},_x000D_
{"country":"india","gender":"female","type":"upper"}];_x000D_
var seq = ["country","type","gender","class"];_x000D_
var treeData = createHieArr(data,seq);_x000D_
console.log(treeData)_x000D_
function createHieArr(data,seq){_x000D_
var hieObj = createHieobj(data,seq,0),_x000D_
hieArr = convertToHieArr(hieObj,"Top Level");_x000D_
return [{"name": "Top Level", "parent": "null",_x000D_
"children" : hieArr}]_x000D_
function convertToHieArr(eachObj,parent){_x000D_
var arr = [];_x000D_
for(var i in eachObj){_x000D_
arr.push({"name":i,"parent":parent,"children":convertToHieArr(eachObj[i],i)})_x000D_
}_x000D_
return arr;_x000D_
}_x000D_
function createHieobj(data,seq,ind){_x000D_
var s = seq[ind];_x000D_
if(s == undefined){_x000D_
return [];_x000D_
}_x000D_
var childObj = {};_x000D_
for(var ele of data){_x000D_
if(ele[s] != undefined){_x000D_
if(childObj[ele[s]] == undefined){_x000D_
childObj[ele[s]] = [];_x000D_
}_x000D_
childObj[ele[s]].push(ele);_x000D_
}_x000D_
}_x000D_
ind = ind+1;_x000D_
for(var ch in childObj){_x000D_
childObj[ch] = createHieobj(childObj[ch],seq,ind)_x000D_
}_x000D_
return childObj;_x000D_
}_x000D_
}
_x000D_
My typescript solution, maybe it helps you:
type ITreeItem<T> = T & {
children: ITreeItem<T>[],
};
type IItemKey = string | number;
function createTree<T>(
flatList: T[],
idKey: IItemKey,
parentKey: IItemKey,
): ITreeItem<T>[] {
const tree: ITreeItem<T>[] = [];
// hash table.
const mappedArr = {};
flatList.forEach(el => {
const elId: IItemKey = el[idKey];
mappedArr[elId] = el;
mappedArr[elId].children = [];
});
// also you can use Object.values(mappedArr).forEach(...
// but if you have element which was nested more than one time
// you should iterate flatList again:
flatList.forEach((elem: ITreeItem<T>) => {
const mappedElem = mappedArr[elem[idKey]];
if (elem[parentKey]) {
mappedArr[elem[parentKey]].children.push(elem);
} else {
tree.push(mappedElem);
}
});
return tree;
}
Example of usage:
createTree(yourListData, 'id', 'parentId');
ES6 Map version :
getTreeData = (items) => {
if (items && items.length > 0) {
const data = [];
const map = {};
items.map((item) => {
const id = item.id; // custom id selector !!!
if (!map.hasOwnProperty(id)) {
// in case of duplicates
map[id] = {
...item,
children: [],
};
}
});
for (const id in map) {
if (map.hasOwnProperty(id)) {
let mappedElem = [];
mappedElem = map[id];
/// parentId : use custom id selector for parent
if (
mappedElem.parentId &&
typeof map[mappedElem.parentId] !== "undefined"
) {
map[mappedElem.parentId].children.push(mappedElem);
} else {
data.push(mappedElem);
}
}
}
return data;
}
return [];
};
/// use like this :
const treeData = getTreeData(flatList);
This is a modified version of the above that works with multiple root items, I use GUIDs for my ids and parentIds so in the UI that creates them I hard code root items to something like 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;
}
( BONUS1 : NODES MAY or MAY NOT BE ORDERED )
( BONUS2 : NO 3RD PARTY LIBRARY NEEDED, PLAIN JS )
( BONUS3 : User "Elias Rabl" says this is the fastest 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": "Chelm",
"Name": "Scarlet"
}];
const expectedDataTree = [{
"ID": 1,
"Phone": "(403) 125-2552",
"City": "Coevorden",
"Name": "Grady",
childNodes: [{
"ID": 2,
"parentID": 1,
"Phone": "(979) 486-1932",
"City": "Chelm",
"Name": "Scarlet",
childNodes : []
}]
}];
expect(createDataTree(dataSet)).toEqual(expectedDataTree);
});
Here is a modified version of Steven Harris' that is plain ES5 and returns an object keyed on the id rather than returning an array of nodes at both the top level and for the children.
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);
My solution:
/**
*
* @param data items array
* @param idKey item's id key (e.g., item.id)
* @param parentIdKey item's key that points to parent (e.g., item.parentId)
* @param noParentValue item's parent value when root (e.g., item.parentId === noParentValue => item is root)
* @param bidirectional should parent reference be added
*/
function flatToTree(data, idKey, parentIdKey, noParentValue = null, bidirectional = true) {
const nodes = {}, roots = {}, leaves = {};
// iterate over all data items
for (const i of data) {
// add item as a node and possibly as a leaf
if (nodes[i[idKey]]) { // already seen this item when child was found first
// add all of the item's data and found children
nodes[i[idKey]] = Object.assign(nodes[i[idKey]], i);
} else { // never seen this item
// add to the nodes map
nodes[i[idKey]] = Object.assign({ $children: []}, i);
// assume it's a leaf for now
leaves[i[idKey]] = nodes[i[idKey]];
}
// put the item as a child in parent item and possibly as a root
if (i[parentIdKey] !== noParentValue) { // item has a parent
if (nodes[i[parentIdKey]]) { // parent already exist as a node
// add as a child
(nodes[i[parentIdKey]].$children || []).push( nodes[i[idKey]] );
} else { // parent wasn't seen yet
// add a "dummy" parent to the nodes map and put the item as its child
nodes[i[parentIdKey]] = { $children: [ nodes[i[idKey]] ] };
}
if (bidirectional) {
// link to the parent
nodes[i[idKey]].$parent = nodes[i[parentIdKey]];
}
// item is definitely not a leaf
delete leaves[i[parentIdKey]];
} else { // this is a root item
roots[i[idKey]] = nodes[i[idKey]];
}
}
return {roots, nodes, leaves};
}
Usage example:
const data = [{id: 2, parentId: 0}, {id: 1, parentId: 2} /*, ... */];
const { nodes, roots, leaves } = flatToTree(data, 'id', 'parentId', 0);
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
}
Answer to a similar question:
https://stackoverflow.com/a/61575152/7388356
You can use Map
object introduced in ES6. Basically instead of finding parents by iterating over the array again, you'll just get the parent item from the array by parent's id like you get items in an array by index.
Here is the simple example:
const 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
}
];
function toTree(arr) {
let arrMap = new Map(arr.map(item => [item.id, item]));
let tree = [];
for (let i = 0; i < arr.length; i++) {
let item = arr[i];
if (item.parentId !== "0") {
let parentItem = arrMap.get(item.parentId);
if (parentItem) {
let { children } = parentItem;
if (children) {
parentItem.children.push(item);
} else {
parentItem.children = [item];
}
}
} else {
tree.push(item);
}
}
return tree;
}
let tree = toTree(people);
console.log(tree);
You can use npm package array-to-tree https://github.com/alferov/array-to-tree. It's convert a plain array of nodes (with pointers to parent nodes) to a nested data structure.
Solves a problem with conversion of retrieved from a database sets of data to a nested data structure (i.e. navigation tree).
Usage:
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
*/
Based on @FurkanO's answer, I created another version that does not mutate the origial data (like @Dac0d3r requested). I really liked @shekhardtu's answer, but realized it had to filter through the data many times. I thought a solution could be to use FurkanO's answer by copying the data first. I tried my version in jsperf, and the results where unfortunately (very) bleak... It seems like the accepted answer is really a good one! My version is quite configurable and failsafe though, so I share it with you guys anyway; here is my contribution:
function unflat(data, options = {}) {
const { id, parentId, childrenKey } = {
id: "id",
parentId: "parentId",
childrenKey: "children",
...options
};
const copiesById = data.reduce(
(copies, datum) => ((copies[datum[id]] = datum) && copies),
{}
);
return Object.values(copiesById).reduce(
(root, datum) => {
if ( datum[parentId] && copiesById[datum[parentId]] ) {
copiesById[datum[parentId]][childrenKey] = [ ...copiesById[datum[parentId]][childrenKey], datum ];
} else {
root = [ ...root, datum ];
}
return root
}, []
);
}
const data = [
{
"account": "10",
"name": "Konto 10",
"parentAccount": null
},{
"account": "1010",
"name": "Konto 1010",
"parentAccount": "10"
},{
"account": "10101",
"name": "Konto 10101",
"parentAccount": "1010"
},{
"account": "10102",
"name": "Konto 10102",
"parentAccount": "1010"
},{
"account": "10103",
"name": "Konto 10103",
"parentAccount": "1010"
},{
"account": "20",
"name": "Konto 20",
"parentAccount": null
},{
"account": "2020",
"name": "Konto 2020",
"parentAccount": "20"
},{
"account": "20201",
"name": "Konto 20201",
"parentAccount": "2020"
},{
"account": "20202",
"name": "Konto 20202",
"parentAccount": "2020"
}
];
const options = {
id: "account",
parentId: "parentAccount",
childrenKey: "children"
};
console.log(
"Hierarchical tree",
unflat(data, options)
);
With the options parameter, it is possible to configure what property to use as id or parent id. It is also possible to configure the name of the children property, if someone wants "childNodes": []
or something.
OP could simply use default options:
input.People = unflat(input.People);
If the parent id is falsy (null
, undefined
or other falsy values) or the parent object does not exist, we consider the object to be a root node.
I had similar issue couple days ago when have to display folder tree from flat array. I didn't see any solution in TypeScript here so I hope it will be helpful.
In my cases main parent were only one, also rawData array don't have to be sorted. Solutions base on prepare temp object like
{parentId: [child1, child2, ...] }
example raw data
const flatData: any[] = Folder.ofCollection([
{id: '1', title: 'some title' },
{id: '2', title: 'some title', parentId: 1 },
{id: '3', title: 'some title', parentId: 7 },
{id: '4', title: 'some title', parentId: 1 },
{id: '5', title: 'some title', parentId: 2 },
{id: '6', title: 'some title', parentId: 5 },
{id: '7', title: 'some title', parentId: 5 },
]);
def of Folder
export default class Folder {
public static of(data: any): Folder {
return new Folder(data);
}
public static ofCollection(objects: any[] = []): Folder[] {
return objects.map((obj) => new Folder(obj));
}
public id: string;
public parentId: string | null;
public title: string;
public children: Folder[];
constructor(data: any = {}) {
this.id = data.id;
this.parentId = data.parentId || null;
this.title = data.title;
this.children = data.children || [];
}
}
SOLUTION: Function that returns tree structure for flat argument
public getTree(flatData: any[]): Folder[] {
const addChildren = (item: Folder) => {
item.children = tempChild[item.id] || [];
if (item.children.length) {
item.children.forEach((child: Folder) => {
addChildren(child);
});
}
};
const tempChild: any = {};
flatData.forEach((item: Folder) => {
const parentId = item.parentId || 0;
Array.isArray(tempChild[parentId]) ? tempChild[parentId].push(item) : (tempChild[parentId] = [item]);
});
const tree: Folder[] = tempChild[0];
tree.forEach((base: Folder) => {
addChildren(base);
});
return tree;
}
It may be useful package list-to-tree Install:
bower install list-to-tree --save
or
npm install list-to-tree --save
For example, have 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-to-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
}];
You can use this "treeify" package from Github here or NPM.
Installation:
$ npm install --save-dev treeify-js
This is a proposal for unordered items. This function works with a single loop and with a hash table and collects all items with their id
. If a root node is found, then the object is added to the result array.
function getTree(data, root) {_x000D_
var o = {};_x000D_
data.forEach(function (a) {_x000D_
if (o[a.id] && o[a.id].children) {_x000D_
a.children = o[a.id].children;_x000D_
}_x000D_
o[a.id] = a;_x000D_
o[a.parentId] = o[a.parentId] || {};_x000D_
o[a.parentId].children = o[a.parentId].children || [];_x000D_
o[a.parentId].children.push(a);_x000D_
});_x000D_
return o[root].children;_x000D_
}_x000D_
_x000D_
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 }] },_x000D_
tree = Object.keys(data).reduce(function (r, k) {_x000D_
r[k] = getTree(data[k], '0');_x000D_
return r;_x000D_
}, {});_x000D_
_x000D_
console.log(tree);
_x000D_
.as-console-wrapper { max-height: 100% !important; top: 0; }
_x000D_
this is what i used in a react 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 }),
}));
usage:
// 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');
output:
[
{
"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"
}
]
}
]```
Source: Stackoverflow.com