fast-tree-builder
fast-tree-builder
is an npm package that allows you to efficiently build trees from iterable data structures. With its optimized algorithm, strong TypeScript typings, and customizable node structure, it provides a reliable solution for organizing and manipulating hierarchical data.
Prerequisites
- You have a list of items,
- where each item is identifiable by a unique value,
- and the items are connected via a parent relation.
Features
-
Efficient Tree Building: The package utilizes an optimized algorithm to construct trees efficiently in
O(n)
time, while maintaining good performance. -
Bi-Directional Tree Traversal: Traverse the built tree in both directions, enabling easy navigation between parent and child nodes.
-
Robust TypeScript Type Definitions: Leverage type safety through extensive TypeScript type definitions. The package includes precise type annotations to improve code reliability and developer workflow.
-
Fully Customizable Node Structure: Tailor the structure of the nodes in the built tree to meet your specific requirements. You have the freedom to define data, parent, and children key names according to your application's needs. To avoid circular references parent links can be turned off which helps generating JSON data.
-
Works on Any Iterable Data: Designed to handle arrays, sets, and other iterable data structures efficiently, ensuring broad applicability.
-
No Sorting Required: The algorithm does not require your input data to be sorted, saving you preprocessing time and effort.
-
Flexible Key and Parent Key Types: You can use any JavaScript value for identifying items. Relations checked with strict (
key === parentKey
) comparison. -
Multiple Root Nodes: Can efficiently construct trees with multiple root nodes, accommodating scenarios that necessitate distinct, separate tree structures within the same dataset.
-
Map of Nodes: Beside the root nodes you can retrieve a
Map
object containing the nodes of the built tree, enabling easy entry on any point of the tree. -
Support for Parent Key Validation: Enables you to validate parent keys while building the tree. When a node missing its parent, an error will be thrown.
-
Support for Tree Validation: Ensures the recieved data structure is an acyclic graph.
Installation
To install fast-tree-builder
, use npm:
npm install fast-tree-builder
or
yarn add fast-tree-builder
Usage
Here are some examples showcasing the usage of fast-tree-builder
and their expected outputs:
Example 1: Basic Tree Building
import buildTree from 'fast-tree-builder';
const items = [
{ id: 1, parent: null, name: 'Root 1' },
{ id: 2, parent: null, name: 'Root 2' },
{ id: 3, parent: 1, name: 'Child 1.1' },
{ id: 4, parent: 1, name: 'Child 1.2' },
{ id: 5, parent: 2, name: 'Child 2.1' },
];
const { roots, nodes } = buildTree(items, {
key: 'id',
parentKey: 'parent',
nodeDataKey: 'data',
nodeParentKey: 'parent',
nodeChildrenKey: 'children',
});
console.log(roots[0].data.name);
// Expected output: Root 1
console.log(roots[0].children[1].data.name);
// Expected output: Child 1.2
console.log(roots[0].children[1].parent.data.name);
// Expected output: Root 1
console.log(roots);
// Expected output: [
// { data: { id: 1, parent: null, name: 'Root 1' }, children: [
// { data: { id: 3, parent: 1, name: 'Child 1.1' }, parent: { ... } },
// { data: { id: 4, parent: 1, name: 'Child 1.2' }, parent: { ... } }
// ] },
// { data: { id: 2, parent: null, name: 'Root 2' }, children: [
// { data: { id: 5, parent: 2, name: 'Child 2.1' }, parent: { ... } }
// ] }
// ]
console.log(nodes);
// Expected output: Map {
// 1 => { data: { id: 1, parent: null, name: 'Root 1' }, children: [
// { data: { id: 3, parent: 1, name: 'Child 1.1' }, parent: { ... } },
// { data: { id: 4, parent: 1, name: 'Child 1.2' }, parent: { ... } }
// ] },
// 2 => { data: { id: 2, parent: null, name: 'Root 2' }, children: [
// { data: { id: 5, parent: 2, name: 'Child 2.1' }, parent: { ... } }
// ] },
// 3 => { data: { id: 3, parent: 1, name: 'Child 1.1' }, parent: { ... } },
// 4 => { data: { id: 4, parent: 1, name: 'Child 1.2' }, parent: { ... } },
// 5 => { data: { id: 5, parent: 2, name: 'Child 2.1' }, parent: { ... } }
// }
Example 2: Customized Node Structure
import buildTree from 'fast-tree-builder';
const items = [
{ key: { n: 1 }, parentKey: null, name: 'Root 1' },
{ key: { n: 2 }, parentKey: null, name: 'Root 2' },
{ key: { n: 3 }, parentKey: { n: 1 }, name: 'Child 1.1' },
{ key: { n: 4 }, parentKey: { n: 1 }, name: 'Child 1.2' },
{ key: { n: 5 }, parentKey: { n: 2 }, name: 'Child 2.1' },
];
const { roots, nodes } = buildTree(items, {
key(item) { return item.key?.n; },
parentKey(item) { return item.parentKey?.n; },
nodeDataKey: false, // merge item data into node
nodeParentKey: 'up',
nodeChildrenKey: 'down',
mapNodeData(item) { return { title: item.name }; },
});
console.log(roots[0].title);
// Expected output: Root 1
console.log(roots[0].down[1].title);
// Expected output: Child 1.2
console.log(roots[0].down[1].up.title);
// Expected output: Root 1
console.log(roots);
// Expected output: [
// { title: 'Root 1', down: [
// { title: 'Child 1.1', up: { ... } },
// { title: 'Child 1.2', up: { ... } }
// ] },
// { title: 'Root 2', down: [
// { title: 'Child 2.1', up: { ... } }
// ] }
// ]
console.log(nodes);
// Expected output: Map {
// 1 => { title: 'Root 1', down: [
// { title: 'Child 1.1', up: { ... } },
// { title: 'Child 1.2', up: { ... } }
// ] },
// 2 => { title: 'Root 2', down: [
// { title: 'Child 2.1', up: { ... } }
// ] },
// 3 => { title: 'Child 1.1', up: { ... } },
// 4 => { title: 'Child 1.2', up: { ... } },
// 5 => { title: 'Child 2.1', up: { ... } }
// }
Example 3: Crazy ideas
import buildTree from 'fast-tree-builder';
const items = [
'0001Root 1',
'0002Root 2',
'0103Child 1.1',
'0104Child 1.2',
'0205Child 2.1',
];
const { roots, nodes } = buildTree(items, {
key(item) { return item.substring(2, 4); },
parentKey(item) { return item.substring(0, 2); },
mapNodeData(item) { return { name: item.substring(4) }; },
nodeDataKey: false, // merge item data into node
});
console.log(roots[0].name);
// Expected output: Root 1
console.log(roots[0].children[1].name);
// Expected output: Child 1.2
console.log(roots);
// Expected output: [
// { name: 'Root 1', children: [
// { name: 'Child 1.1', parent: { ... } },
// { name: 'Child 1.2', parent: { ... } }
// ] },
// { name: 'Root 2', children: [
// { name: 'Child 2.1', parent: { ... } }
// ] }
// ]
Documentation
buildTree(items: Iterable<T>, options: BuildTreeOptions): TreeResult<T>
Builds a tree from the given iterable items
using the specified options
.
Parameters
-
items
: An iterable data structure containing the items to build the tree from. -
options
: An object specifying the build options. It has the following properties:-
key
: (Optional) The key used to identify items. It can be a string, number, symbol, or a function that extracts the key from an item. Defaults to'id'
. -
parentKey
: (Optional) The key used to identify the parent of each item. It can be a string, number, symbol, or a function that extracts the parent key from an item. Defaults to'parent'
. -
nodeDataKey
: (Optional) The key used to store the item's data in each node. It can be a string, number, symbol, or false if the data should be merged directly into the node. Defaults to'data'
. -
nodeParentKey
: (Optional) The key used to store the parent node in each node. It can be a string, number, symbol, or false if the parent node should not be included. Defaults to'parent'
. -
nodeChildrenKey
: (Optional) The key used to store the children nodes in each node. It can be a string, number, symbol. Defaults to'children'
. -
mapNodeData
: (Optional) A function that maps an item to its corresponding node data. It allows transforming the item before assigning it to the node. Defaults toundefined
. -
validateParentKeys
: (Optional) An iterable containing parent key values that can be accepted as root nodes. If provided, any item with a parent key not present in this iterable will cause an error to be thrown. Defaults toundefined
. -
validateTree
: (Optional) A boolean flag that determines whether to validate the resulting data structure. If the structure is a cyclic graph, anError
will be thrown. Requires additionalO(n)
time to compute. Defaults tofalse
.
-
Returns
An object with the following properties:
-
roots
: An array of the root nodes of the built tree. -
nodes
: AMap
object containing all nodes of the built tree, with keys corresponding to their identifiers.
Throws Error
when:
- A duplicate identifier is recieved,
- or
validateParentKeys
is set and an invalid parent key is recieved, - or
validateTree
is set totrue
and a cyclic graph is the result.
Comparison with other tree building libraries
The package aims to be feature complete and highly customizable, which usually opposes with performance. There are other packages that may be more performant but lacks features that I really needed in my daily coding. In standard scenarios this package should perform more than enough and nearly as good as other packages.
For scenarios where performance is critical, consider implementing a tailored, optimized algorithm. It could be as simple as:
const roots = [];
const nodes = new Map();
for (const item of items) {
let node = nodes.get(item.id);
if (!node) {
node = {};
nodes.set(item.id, node);
}
node.data = item; // Or Object.assign(node, item);
if (item.parentId) {
let parent = nodes.get(item.parentId);
if (!parent) {
parent = {};
nodes.set(item.parentId, parent);
}
if (!parent.children) parent.children = [];
parent.children.push(node);
node.parent = parent;
} else {
roots.push(node);
}
}
Contributions
Contributions to fast-tree-builder
are welcome! If you have any bug reports, feature requests, or improvements, please open an issue on the GitHub repository.
License
fast-tree-builder
is licensed under the MIT License.