Neverending Pile of Messages
Publish your own packages to the world's most popular software ecosystem with npm Pro.Get started »

performant-array-to-tree

1.2.0 • Public • Published

Performant array to tree

npm version minified size CircleCI Coverage Status Dependency Status devDependency Status typings included JavaScript Style Guide npm license

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.

Why another package

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.

Installation

yarn add performant-array-to-tree

or if using npm

npm install --save performant-array-to-tree

Usage

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: [] },
    ] },
]

Configuration

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 origina 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: [] },
    ] },
]

TypeScript

This project includes types, just import the module as usual:

import { arrayToTree } from 'performant-array-to-tree'
 
const tree = arrayToTree(array)

Install

npm i performant-array-to-tree

DownloadsWeekly Downloads

1,829

Version

1.2.0

License

MIT

Unpacked Size

95.5 kB

Total Files

16

Last publish

Collaborators

  • avatar