Converts an array of items with ids and parent ids to a nested tree in a performant O(n) way. Runs in browsers and node.
Other packages have stricter assumptions or are not as performant, as they often use multiple loops or recursion. For example:
o-unflatten requires the input to be ordered such that parent nodes always come before their children. array-to-tree uses two loops (runs with O(2n)), one for grouping all items by their parents, and one for creating the tree. un-flatten-tree uses 2 nested loops (runs even worse with O(n^2)).
This implementation does not require any order of items in the input array and focuses on runtime performance. By only using a single loop (runs with 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: 'ü'}, ]) // output tree === [ { 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 itemparentId: key of the parent's id field of the item
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' }) // output tree === [ { 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: [] }, ] }, ]This project includes types, just import the module as usual:
import * as arrayToTree from 'performant-array-to-tree' const tree = arrayToTree(array)