Build tree array from flat array in javascript

Question

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
 }
 }
 ]
}

• bfavaretto: There are several ways to do that, did you try anything yet?
• Donnie D'Amato: I assume that a parentId of 0 means there is no parent id and should be the top layer.
• Gangadhar Jannu: Usually these kind of tasks required extensive working knowledge objects. Good question

Answer 1

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');

Answer 2

Answer to a similar question:

https://stackoverflow.com/a/61575152/7388356

UPDATE

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);

Edit crazy-williams-glgj3

• JeffRSon: While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review
• Yusuf: Ok, Added the main idea and gave a sample example,

Answer 3

1. without third party library
2. no need for pre-ordering array
3. you can get any portion 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
 }

Test it on Jsfiddle

Answer 4

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)

hope it helps someone