Converts an array of items with ids and parent ids to a nested tree in a performant way (time complexity O(n)). Runs in browsers and node.
Other packages have stricter assumptions or are not as performant, as they often use nested loops or recursion. For example:
o-unflatten requires the input to be ordered such that parent nodes always come before their children. un-flatten-tree uses 2 nested loops (time complexity O(n^2)).
This implementation does not require any order of items in the input array and focuses on runtime performance. It is the fastest amongst 4 different packages, you can find the benchmarks here. It uses an index and a single loop (time complexity O(n)). It was inspired by this discussion on StackOverflow.
yarn add performant-array-to-tree
or if using npm
npm install --save performant-array-to-tree
const tree = arrayToTree([ { id: '4', parentId: null, custom: 'abc' }, { id: '31', parentId: '4', custom: '12' }, { id: '1941', parentId: '418', custom: 'de' }, { id: '1', parentId: '418', custom: 'ZZZz' }, { id: '418', parentId: null, custom: 'ü'}, ])Which results in the following array:
[ { data: { id: '4', parentId: null, custom: 'abc' }, children: [ { data: { id: '31', parentId: '4', custom: '12' }, children: [] }, ] }, { data: { id: '418', parentId: null, custom: 'ü'}, children: [ { data: { id: '1941', parentId: '418', custom: 'de' }, children: [] }, { data: { id: '1', parentId: '418', custom: 'ZZZz' }, children: [] }, ] }, ]You can provide a second argument to arrayToTree with configuration options. Right now, you can set the following:
id: key of the id field of the item. Default:"id"parentId: key of the parent's id field of the item. Default:"parentId"dataField: key which will contain all properties/data of the original items. Set to null if you don't want a container. Default:"data"
Example:
const tree = arrayToTree([ { num: '4', ref: null, custom: 'abc' }, { num: '31', ref: '4', custom: '12' }, { num: '1941', ref: '418', custom: 'de' }, { num: '1', ref: '418', custom: 'ZZZz' }, { num: '418', ref: null, custom: 'ü'}, ], { id: 'num', parentId: 'ref' })Which produces:
[ { data: { num: '4', ref: null, custom: 'abc' }, children: [ { data: { num: '31', ref: '4', custom: '12' }, children: [] }, ] }, { data: { num: '418', ref: null, custom: 'ü'}, children: [ { data: { num: '1941', ref: '418', custom: 'de' }, children: [] }, { data: { num: '1', ref: '418', custom: 'ZZZz' }, children: [] }, ] }, ]Example with no data field:
const tree = arrayToTree([ { id: '4', parentId: null, custom: 'abc' }, { id: '31', parentId: '4', custom: '12' }, { id: '1941', parentId: '418', custom: 'de' }, { id: '1', parentId: '418', custom: 'ZZZz' }, { id: '418', parentId: null, custom: 'ü'}, ], { dataField: null })Which produces:
[ { id: '4', parentId: null, custom: 'abc', children: [ { id: '31', parentId: '4', custom: '12', children: [] }, ] }, { id: '418', parentId: null, custom: 'ü', children: [ { id: '1941', parentId: '418', custom: 'de', children: [] }, { id: '1', parentId: '418', custom: 'ZZZz', children: [] }, ] }, ]This project includes types, just import the module as usual:
import { arrayToTree } from 'performant-array-to-tree' const tree = arrayToTree(array)