performant-array-to-tree

Performant array to tree

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.

Why another package

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.

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: 'ü'},
])

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

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

TypeScript

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

import * as arrayToTree from 'performant-array-to-tree'

const tree = arrayToTree(array)