philipstanislaus/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.js.

Performant array to tree

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. Also works with nested properties (e. g. "nested.parentId"). Default: "id".
• parentId: Key of the parent's id field of the item. Also works with nested properties (e. g. "nested.parentId"). Default: "parentId".
• nestedIds: Option to enable/disable nested ids. Default: true.
• childrenField: Key which will contain all child nodes of the parent node. Default: "children"
• dataField: Key which will contain all properties/data of the original items. Set to null if you don't want a container. Default: "data"
• throwIfOrphans: Option to throw an error if the array of items contains one or more items that have no parents in the array or if the array of items contains items with a circular parent/child relationship. This option has a small runtime penalty, so it's disabled by default. When enabled, the function will throw an error containing the parentIds that were not found in the items array, or in the case of only circular item relationships a generic error. The function will throw an error if the number of nodes in the tree is smaller than the number of nodes in the original array. When disabled, the function will just ignore orphans and circular relationships and not add them to the tree. Default: false
• rootParentIds: Object with parent ids as keys and true as values that should be considered the top or root elements of the tree. This is useful when your tree is a subset of full tree, which means there is no item whose parent id is one of undefined, null or ''. The array you pass in will be replace the default value. undefined and null are always considered to be rootParentIds. For more details, see #23. Default: {'': true}
• assign: Option that enables Object.assign instead of the spread operator to create an item in the tree when dataField is null. This is useful if your items have a prototype that should be maintained. If enabled and dataField is null, the original node item will be used, and the children property will be assigned, calling any setters on that field. If dataField is not null, this option has no effect, since the original node will be used under the dataField of a new object. If you are unsure whether you need to enable this, it's likely fine to leave it disabled. Default: false

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", childrenField: "nodes" }
);

Which produces:

[
  {
    data: { num: "4", ref: null, custom: "abc" },
    nodes: [{ data: { num: "31", ref: "4", custom: "12" }, nodes: [] }],
  },
  {
    data: { num: "418", ref: null, custom: "ü" },
    nodes: [
      { data: { num: "1941", ref: "418", custom: "de" }, nodes: [] },
      { data: { num: "1", ref: "418", custom: "ZZZz" }, nodes: [] },
    ],
  },
];

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

Example with nested id/parentId properties:

const tree = arrayToTree(
  [
    { num: { id: "4" }, parent: { parentId: null }, custom: "abc" },
    { num: { id: "31" }, parent: { parentId: "4" }, custom: "12" },
  ],
  { id: "num.id", parentId: "parent.parentId" }
);

Which produces:

[
  {
    data: { num: { id: "4" }, parent: { parentId: null }, custom: "abc" },
    children: [
      {
        data: { num: { id: "31" }, parent: { parentId: "4" }, custom: "12" },
        children: [],
      },
    ],
  },
];

TypeScript

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

import { arrayToTree } from "performant-array-to-tree";

const tree = arrayToTree(array);

Development

yarn version to create a new version npm login npm publish --access public to publish it to npm

performant-array-to-tree's Issues

feature request: support pick item props

const tree = arrayToTree(arr, {
  transform: ['id',  'key1'],
  // transform: item => { return { id: item.id, key1: item.key1 } },
});

Prototype is Losted

performant-array-to-tree/src/arrayToTree.ts

Line 88 in efe07a8

lookup[itemId] = {

change

lookup[itemId] = {
    ...item,
    [conf.childrenField]: lookup[itemId][conf.childrenField],
  };

to:

lookup[itemId] = Object.assign(item, {
  [conf.childrenField]: lookup[itemId][conf.childrenField]
})

Fix coveralls reporting by migrating to IstanbulJS

Line coverage only decreased in build folder, not in source code, but the current remapping configuration does not account for that. Reason is that TypeScript's _assign stub is only used partly.

ParentID 0 returns empty array

Hi,

I noticed a problem that is problematic when parentId is 0. That happened when I was pulling categories from WooCommerce.
Example Object

[
  {
    id: 17,
    name: 'child 1',
    slug: 'child-1',
    parent: 16,
    description: '',
    display: 'default',
    image: null,
    menu_order: 0,
    count: 0,
    _links: { self: [Array], collection: [Array], up: [Array] }
  },
  {
    id: 18,
    name: 'child 1 1',
    slug: 'child-1-1',
    parent: 17,
    description: '',
    display: 'default',
    image: null,
    menu_order: 0,
    count: 0,
    _links: { self: [Array], collection: [Array], up: [Array] }
  },
  {
    id: 16,
    name: 'Parent Catgory',
    slug: 'parent-catgory',
    parent: 0,
    description: 'parent category',
    display: 'default',
    image: null,
    menu_order: 0,
    count: 0,
    _links: { self: [Array], collection: [Array] }
  },
  {
    id: 15,
    name: 'Uncategorized',
    slug: 'uncategorized',
    parent: 0,
    description: '',
    display: 'default',
    image: null,
    menu_order: 0,
    count: 1,
    _links: { self: [Array], collection: [Array] }
  }
]

Regards

ParentId not in the array

May I know how do you handle the situation where an item has parentId (i.e. it is not null) that does not match the id of any other items in the array, and therefore the item itself should be considered a root element?

Add `rootParentId` option to fit the case when all rows contain a valid parentId string

Why

In most cases, our tree list contains a row whose parentId field is one of null / undefined / '', but if the tree list is a subset of original tree list, chances are that the transform result is not right, no matter the throwIfOrphans option is set to true or false

example:

import { arrayToTree } from 'performant-array-to-tree'

const list = [
  { id: "aaa", parentId: "notexist" },
  { id: "bbb", parentId: "aaa" },
  { id: "ccc", parentId: "bbb" },
  { id: "ddd", parentId: "bbb" },
];
const result = arrayToTree(list, {
  dataField: null,
});
console.log(JSON.stringify(result, null, 2)); // the output is []

Suggestion

If we add an option named rootParentId, items whose parentId equals rootParentId will be treat as a root item.

The above code's output should be like this

const result = arrayToTree(list, {
  dataField: null,
  rootParentId: "notexist",
});

[
  {
    "id": "aaa",
    "parentId": "notexist",
    "children": [
      {
        "id": "bbb",
        "parentId": "aaa",
        "children": [
          {
            "id": "ccc",
            "parentId": "bbb",
            "children": []
          },
          {
            "id": "ddd",
            "parentId": "bbb",
            "children": []
          }
        ]
      }
    ]
  }
]

How

Add rootParentId into option, then replace

if (parentId === null || parentId === undefined || parentId === '') {
      rootItems.push(TreeItem)
    }

with

if (parentId === null || parentId === undefined || parentId === '' || parentId === conf.rootParentId) {
      // is a root item
      rootItems.push(TreeItem)
    }

Of course we can also make rootParentId an array, the initial value is [null, undefined, ''] and will later be merged with user defined rootParentIds

null/undefined exception with nested id and parentId properties

Hi there,
I've tried to use this library for constructing a tree on a application I'm developing and while it has the awesome feature of using nested id and parentId properties I've noticed a potential bug on it.

The data that I'm getting from an API has the following structure:

var performantArrayToTree = require("performant-array-to-tree");

const data = [
  {
    id: 1,
    title: "Some title",
    parent: null
  },
  {
    id: 125,
    title: "Some title 2",
    parent: {
      id: 1,
    },
  },
];

console.log(performantArrayToTree.arrayToTree(data, {
    parentId: 'parent.id',
}));

Expected result:

[
  {
    data: { id: 1, title: "Some title", parent: null },
    children: [
      {
        data: { id: 125, title: "Some title 2", parent: null },
        children: [],
      }
    ]
  }
]

Result I've gotten:
TypeError: Cannot read property 'parentId' of null

My guess is that the problem is in the following function:

function getNestedProperty(item: Item, nestedProperty: string) {
  return nestedProperty.split(".").reduce((o, i) => o[i], item);
}

Since it's accessing the object o which in my case is null with the key of i it will throw an exception. A potential fix is to check if o is null or undefined and if it is the reduce function should return null as well.

function getNestedProperty(item: Item, nestedProperty: string) {
  return nestedProperty.split(".").reduce((o, i) => (o === null || o === undefined) ? null : o[i], item);
}

Add option to include parent in the result

Is there a way to include a back reference to the parent from each nested child.

{ id: ".key" } does not work

Using ".key" as id does not work.

My guess is that the code references the element as item.id and not item[id].
Since ".key" contains a dot it needs to be accessed with item[".key"].

I do not know Typescript but I think this is as an example of accessing with .id compared to [id]:

performant-array-to-tree/src/arrayToTree.ts

Line 57 in 594f4d1

const itemId = getNestedProperty(item, conf.id);

Tree and Node function

Hi !
I am new to JavaScript Tree data structure, so sorry if my question is irrelevant,
I wanted to know if you plan usual tree and node method (search for a node, add a child, delete a node...), as describe on the following link for eg ?

https://code.tutsplus.com/articles/data-structures-with-javascript-tree--cms-23393

As far as I undestood I didnt see any other array to tree npm module which embeds such features, and as your script seems more efficient, it could bice to have these !

Thanks for listening :)

Add multiple parent ids

It would be great to add an option to add a list of parent ids, so that the element gets duplicated and added to the respective parents objects.

Parent ID Issue

When there are multiple parents (at the same highest level) with multiple children, the result is [] empty.

const data = [
    {
        "Id": "51eba4ed-d724-48f6-9627-16704ef56b7a",
        "LastModified": "2022-04-20T14:46:58Z",
        "Title": "Navigation",
        "Description": "",
        "UrlName": "navigation",
        "Name": "navigation",
        "Synonyms": "",
        "TaxonomyId": "e5cd6d69-1543-427b-ad62-688a99f5e7d4",
        "Ordinal": -11,
        "FullUrl": "/navigation",
        "ParentId": "00000000-0000-0000-0000-000000000000",
        "Provider": "OpenAccessDataProvider"
    },
    {
        "Id": "718c5b9b-b0fd-4c84-96da-36566104efa8",
        "LastModified": "2022-04-20T13:23:49Z",
        "Title": "Video Type",
        "Description": "",
        "UrlName": "video-type",
        "Name": "video-type",
        "Synonyms": "",
        "TaxonomyId": "e5cd6d69-1543-427b-ad62-688a99f5e7d4",
        "Ordinal": -7,
        "FullUrl": "/video-type",
        "ParentId": "00000000-0000-0000-0000-000000000000",
        "Provider": "OpenAccessDataProvider"
    },
    {
        "Id": "3c59b053-38bd-46e3-8927-42d6320142a8",
        "LastModified": "2022-04-20T14:45:59Z",
        "Title": "Vimeo",
        "Description": "",
        "UrlName": "vimeo",
        "Name": "vimeo",
        "Synonyms": "",
        "TaxonomyId": "e5cd6d69-1543-427b-ad62-688a99f5e7d4",
        "Ordinal": -9,
        "FullUrl": "/video-type/vimeo",
        "ParentId": "718c5b9b-b0fd-4c84-96da-36566104efa8",
        "Provider": "OpenAccessDataProvider"
    },
    {
        "Id": "4f2a80e5-6712-4c92-a174-66b6f8786752",
        "LastModified": "2022-04-05T16:13:54Z",
        "Title": "In-vehicle Applications",
        "Description": "",
        "UrlName": "in-vehicle-applications",
        "Name": "in-vehicle-applicationseaa47100-39da-44f5-9e49-2820a25fd977",
        "Synonyms": "",
        "TaxonomyId": "e5cd6d69-1543-427b-ad62-688a99f5e7d4",
        "Ordinal": -5,
        "FullUrl": "/navigation/apps/in-vehicle-applications",
        "ParentId": "3b2d0dff-808a-4c38-8a49-f11fd032fc5e",
        "Provider": "OpenAccessDataProvider"
    },
    {
        "Id": "3610dbd5-4be8-415c-9d6b-94ac87f06976",
        "LastModified": "2022-04-05T16:14:21Z",
        "Title": "Mobile Applications",
        "Description": "",
        "UrlName": "mobile-applications",
        "Name": "mobile-applications100b5984-8b91-4a53-b603-82bbd27ae62e",
        "Synonyms": "",
        "TaxonomyId": "e5cd6d69-1543-427b-ad62-688a99f5e7d4",
        "Ordinal": -6,
        "FullUrl": "/navigation/apps/mobile-applications",
        "ParentId": "3b2d0dff-808a-4c38-8a49-f11fd032fc5e",
        "Provider": "OpenAccessDataProvider"
    },
    {
        "Id": "7d1a5c07-1b9d-421f-9902-a741c97df2fe",
        "LastModified": "2022-04-20T14:45:32Z",
        "Title": "YouTube",
        "Description": "",
        "UrlName": "youtube",
        "Name": "youtube",
        "Synonyms": "",
        "TaxonomyId": "e5cd6d69-1543-427b-ad62-688a99f5e7d4",
        "Ordinal": -8,
        "FullUrl": "/video-type/youtube",
        "ParentId": "718c5b9b-b0fd-4c84-96da-36566104efa8",
        "Provider": "OpenAccessDataProvider"
    },
    {
        "Id": "6af37344-49df-4af3-99d3-ad90356f5264",
        "LastModified": "2022-04-20T14:46:33Z",
        "Title": "Brightcove",
        "Description": "",
        "UrlName": "brightcove",
        "Name": "brightcove",
        "Synonyms": "",
        "TaxonomyId": "e5cd6d69-1543-427b-ad62-688a99f5e7d4",
        "Ordinal": -10,
        "FullUrl": "/video-type/brightcove",
        "ParentId": "718c5b9b-b0fd-4c84-96da-36566104efa8",
        "Provider": "OpenAccessDataProvider"
    },
    {
        "Id": "3b2d0dff-808a-4c38-8a49-f11fd032fc5e",
        "LastModified": "2022-04-20T14:47:16Z",
        "Title": "Apps",
        "Description": "",
        "UrlName": "apps",
        "Name": "appsbeb61f16-48a0-4368-acc6-b34aa7c1804e",
        "Synonyms": "",
        "TaxonomyId": "e5cd6d69-1543-427b-ad62-688a99f5e7d4",
        "Ordinal": -4,
        "FullUrl": "/navigation/apps",
        "ParentId": "51eba4ed-d724-48f6-9627-16704ef56b7a",
        "Provider": "OpenAccessDataProvider"
    }
];

const result = arrayToTree(data, {
    id: "Id",
    parentId: "ParentId",
    rootParentIds: {
        "00000000-0000-0000-0000-000000000000": true,
    },
}
console.log(result);
// output
// [] length 0

[Feature Request] Pass type for data property with Generics

Thanks for your helpful package.

data property always returns type any.
I think it would be very useful if we could pass type with Generics.

throwIfOrphans: true and input array elements order

Consider a tree with 4 elements like this:

{
  "id": "root",
  "parent_id": null,
  "bar": "bar",
  "children": [
    {
      "id": "2",
      "parent_id": "root",
      "foo": "bar",
      "children": []
    },
    {
      "id": "1",
      "parent_id": "root",
      "foo": "bar",
      "children": [
        {
          "id": "1-1",
          "parent_id": "1",
          "foo": "bar",
          "children": []
        }
      ]
    }
  ]
}

As you may see there is multi level nesting in this tree.

When I break this tree into individual elements and try to build it with option throwIfOrphans: true it will throw. It should not, because there are actually no orphans.

This issue comes from the order of items in the array passed into the arrayToTree function.

To reproduce:

const tree = arrayToTree(
  [
    { id: '2', parent_id: 'root', foo: 'bar' },
    { id: '1-1', parent_id: '1', foo: 'bar' },
    { id: '1', parent_id: 'root', foo: 'bar' },
    { id: 'root', parent_id: null, bar: 'bar' },
  ],
  {
    id: 'id',
    parentId: 'parent_id',
    childrenField: 'children',
    dataField: null,
    throwIfOrphans: true,
  },
);

Results:

Error: The items array contains orphans that point to the following parentIds: [1]. These parentIds do not exist in the items array. Hint: prevent orphans to result in an error by passing the following option: { throwIfOrphans: false }

Now when you change the order of elements in the array it will not throw:

const tree = arrayToTree(
  [
    { id: '2', parent_id: 'root', foo: 'bar' },
    { id: '1', parent_id: 'root', foo: 'bar' },
    { id: '1-1', parent_id: '1', foo: 'bar' },
    { id: 'root', parent_id: null, bar: 'bar' },
  ],
  {
    id: 'id',
    parentId: 'parent_id',
    childrenField: 'children',
    dataField: null,
    throwIfOrphans: true,
  },
);

Meaning that the input array order matters. The error is misleading in this particular case.

Enable nested id and parentId properties

Here's my data structure:

    const array = [
        {  data: { id: 'id1', parent: 'idparent' , otherdata...} },
        {  data: { id: 'id2', parent: 'id1' , otherdata...} },
        {  data: { id: 'id3', parent: 'id1' , otherdata...} }
    ]

id and parentId are nested inside data in my case, and I'd bet it is not uncommon.

Would you amend your code this way to make this scenario work?

Add this:

    const getItemNestedProperty = (item: Item, nestedProperty: string): string => {
	return nestedProperty.split('.').reduce((o, i) => o[i], item)
    }

Replace

    const itemId = item[conf.id]
    const parentId = item[conf.parentId]

with:

    const itemId = getItemNestedProperty(item, conf.id)
    const parentId = getItemNestedProperty(item, conf.parentId)

Thanks!

Would you like to try my “@zhengxs/js.tree”，the same idea

We had very similar ideas, but it was a bit complicated at the time.

google translate

https://github.com/zhengxs2018/common-algorithm/blob/master/src/tree.ts

Now i refactor，Removed a lot of useless logic, more lightweight。

google translate

https://github.com/zhengxs2018/js.tree/blob/main/src/transform/toTree.ts

Maybe we can refer to each other.

google translate

const ROOT_ID = '__ROOT__'

function toTree(data, options = {}) {
  const root = _.defaultTo(options.root, ROOT_ID)
  const idKey = _.defaultTo(options.idKey, 'id')
  const parentKey = _.defaultTo(options.parentKey, 'parentId')
  const childrenKey = _.defaultTo(options.childrenKey, 'children')

  const transform = _.defaultTo(options.transform, (x) => x)

  const nodes = {}

  let i = data.length
  while (i--) {
    const row = data[i]

    // 获取节点ID
    const id = row[idKey]

    // id 必须存在
    assert(!_.isNil(id), `id is required, in ${i}.`)

    // 数据结构转换
    const node = transform(row)

    // 支持过滤掉某些数据
    if (_.isNil(node)) continue

    // 获取子级元素
    const children = nodes[id]
    if (children) {
      node[childrenKey] = children
    } else {
      nodes[id] = node[childrenKey] = []
    }

    // 获取上级节点ID
    const parentId = _.defaultTo(row[parentKey], ROOT_ID)

    // 获取同级元素
    const siblings = nodes[parentId]
    if (siblings) {
      siblings.push(node)
    } else {
      nodes[parentId] = [node]
    }
  }

  return exporter(nodes, root)
}

function exporter(nodes, root) {
  if (typeof root === 'function') {
    return root(nodes) || []
  }

  return nodes[_.defaultTo(root, ROOT_ID)] || []
}

Consider using spread syntax

Currently your implementation places all of the data from the nodes inside a "data" field. Have you considered instead using the spread syntax to maintain the structure of the data being put into trees and simply placing the new children array alongside them? I don't know what kind of performance overhead this would entail just wondering if this was a conscious choice.

Is there a way to omit children key if there is no child nodes?

Return child nodes in tree structure?

Is there a way to return specific child nodes in tree structure?

Add support for parentId = undefined or Integer?

First, thank you @philipstanislaus for building this nice and helpful tool!

I ran in some issues while trying to use it on a project, which I could track down to these points:

• Items are ignored, if their parentId is undefined.
• Items are ignored, if their parentId is 0.

Looking at the code, I saw, that you expect IDs to be strings. My project uses Integers with parentId: 0 for Root-Items. So no surprise it didn’t work out.

Would you mind:

• adding support for Integer IDs?
• allowing undefined (= nonexisting) and 0 (Int) as values of parentId in addition to null?

I would submit a PR, but I’m not used programming in TypeScript. :) Thank you in advance.

Add support for parentId as empty string ("")

Somewhat related to #11 .

We have a project in which id's are represented as string. We run into problems when parentId === "" (the items are ignored/the tree is not building). We can solve the issue by replacing all empty strings by null, but this is a bit cumbersome.

Would it be possible to support empty strings in addition to null, undefined and 0?

We also noticed that there is no output (warnings/errors) in the console when tree building fails. This could help identify problems early on and would be nice to have :)

Cross reference array gives an empty array

var performantArrayToTree = require("performant-array-to-tree")

console.log(performantArrayToTree.arrayToTree([
    { num: "4", ref: "31", custom: "abc" },
    { num: "31", ref: "4", custom: "12" },
  ],
  { id: "num", parentId: "ref", childrenField: "nodes", throwIfOrphans: true }
));

// result = []

version: 1.9.1

Actually, I don't have a strong opinion on the expected result from this situation. But it seems strange that the lib silently cut an array. Probably it should be an error?

Add support for custom "children" value if a node doesn't have children?

Add an option emptyChildren, so we can change the default empty children value. It may be like

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, emptyChildren: node => null }
);

Which produces:

[
  {
    id: "4",
    parentId: null,
    custom: "abc",
    children: [{ id: "31", parentId: "4", custom: "12", children: null }],
  },
  {
    id: "418",
    parentId: null,
    custom: "ü",
    children: [
      { id: "1941", parentId: "418", custom: "de", children: null },
      { id: "1", parentId: "418", custom: "ZZZz", children: null },
    ],
  },
];

---

Sometime we can do more things:

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, emptyChildren: node => { node.isLeaf=true; return null; } }
);

Which produces:

[
  {
    id: "4",
    parentId: null,
    custom: "abc",
    children: [{ id: "31", parentId: "4", custom: "12", children: null, isLeaf: true }],
  },
  {
    id: "418",
    parentId: null,
    custom: "ü",
    children: [
      { id: "1941", parentId: "418", custom: "de", children: null, isLeaf: true },
      { id: "1", parentId: "418", custom: "ZZZz", children: null, isLeaf: true },
    ],
  },
];