versatile-tree

v1.3.10

Published

9 months ago

A highly versatile tree structure for JavaScript.

Downloads

111

Documentation

Read the official documentation.

Overview

This library contains a highly versatile tree structure for JavaScript.

The TreeNode class is simple yet highly versatile:

It can store arbitrary data and children and can be constructed from an object.
When not at the root, it can access its siblings, children, and root, and can be searched.
It can be converted to an object, to JSON, and from JSON easily.

See the Quick Start section below for examples.

Demo - React-Based Tree Editor

This library can be used for applications needing a tree structure.

See below for a demo using this library to power a React-based tree editor.

👁️ View Demo - React-Based Tree Editor

Features include:

🌴 Tree structure in JS
- Construct and use tree structures in JavaScript easily.
🔁 Easy conversion to/from JSON
- Easily convert the entire tree, or a subsection, to and from JSON.
🎯 Node paths and selection paths
- Get a path array to any node, and selection paths for instant selection of nodes.
🆔 IDs are optional
- Versatility is the name of the game. This tree library supports nodes without IDs!
👨‍👩‍👧‍👦 Sibling support
- Get left/right siblings, or add a siblings to any sub-root node. Full sibling support!
🔍 Find and walk
- Find nodes by ID or custom logic, and walk the tree.
📄 Deep cloning
- Easily deep clone the entire tree, or any tree node.
🤴 Ancestor and descendent checking
- Determine if any node is an ancestor or descendant of another.
✨ Much more!
- See the full API below!

Donate

If this project helped you, please consider buying me a coffee or sponsoring me. Your support is much appreciated!

Installation

npm i versatile-tree

Quick Start

import { TreeNode, Tree } from 'versatile-tree';

const tree = new Tree();
const node = tree.addChildData({id: 1});
node.addChildData({id: 2});
node.addSiblingData({id: 3})

// Convert entire tree to JSON
const treeJson = node.getRoot().toJSON();

// Build tree from JSON
const builtTree = TreeNode.fromJSON(treeJson);

TreeNode/Tree API

A Tree alias exists for TreeNode -- in this library, they are interchangeable.

Class Functions

Constructor

new TreeNode(data: Record<string, any> = {}, options: TreeNodeOptions = TreeNode.defaultTreeNodeOptions)

Construct a new TreeNode using the provided data. The data can include arbitrary properties with an optional children array. The default property name for the array of children is "children". This can be customized via options.childrenPropertyName.

The constructor will recursively create TreeNodes for all children. All other properties will be stored as data for each node.

For example, given a nested object such as:

{ id: 1, children: [
    { id: 2 },
    { id: 3, children: [
        { id: 4 },
        { id: 5 }
      ]
    }
  ]
}

In this case, each node will have data containing the id property, and all children will be turned into TreeNodes themselves.

To turn the TreeNode back into an object at a later time, use toObject(), and to turn it into a JSON string, use toJSON(). To construct a TreeNode from JSON, use TreeNode.fromJSON().

| Param | Description | | --------- | -------------------------------------------------------------------------------------------------------------------------- | | data | Optional. An object containing data for the node, plus optional children with subnodes. | | options | Optional (pun intended). The options for the TreeNode. Falls back on TreeNode.defaultTreeNodeOptions when not specified. |

getData

getData()

Return the data for this node, without the children property.

To get data and all descendants, including children, for this node, use toObject().

| Returns | | ------------------------------------------------------ | | The data for this node, without the children property. |

setData

setData(newData: Record<string, any>, replaceChildren = false)

Sets the data for this node. By default, the children property is ignored.

To replace children, pass the replaceChildren argument value as true.

| Param | Description | | ----------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | newData | The new data for this node. | | replaceChildren | Optional. When true, children of the node will be replaced with the children in the data. When false, the children property is ignored and only the node's data is set. Default false. |

getChildrenPropertyName

getChildrenPropertyName()

Returns the property name used for children.

| Returns | | ------------------------------------ | | The property name used for children. |

getOptions

getOptions()

Return the options configured for this node.

| Returns | | ------------------------------------- | | The options configured for this node. |

hasParent

hasParent(): boolean

Returns true if this node has a parent, false otherwise.

When a node has no parent, it is the root. You can also use isRoot() to check for this case.

| Returns | | ------------------------------------------------ | | True if this node has a parent, false otherwise. |

isRoot

isRoot(): boolean

Returns true if this node is the root (has no parent), false otherwise.

When a node has a parent, it is not the root. You can also use hasParent() to check for this case.

| Returns | | --------------------------------------------------------------- | | True if this node is the root (has no parent), false otherwise. |

equals

equals(node: TreeNode): boolean

Returns true if the provided node is equal to this node.

This operation uses the equals function provided in the TreeNode options, and uses === equality by default when an equals function is not specified.

| Param | Description | | ------ | ------------------------------- | | node | The node to check for equality. |

| Returns | | ------------------------------------------------ | | True if the provided node is equal to this node. |

isDescendantOf

isDescendantOf(node: TreeNode)

Returns true if this node is a descendant of, or below, the provided node. False otherwise.

| Param | Description | | ------ | ------------------ | | node | The node to check. |

| Returns | | ----------------------------------------------------------------------------------- | | True if this node is a descendant of, or below, the provided node. False otherwise. |

isAncestorOf

isAncestorOf(node: TreeNode)

Returns true if this node is an ancestor of, or above, the provided node. False otherwise.

| Param | Description | | ------ | ------------------ | | node | The node to check. |

| Returns | | ---------------------------------------------------------------------------------- | | True if this node is an ancestor of, or above, the provided node. False otherwise. |

addChildNode

addChildNode(node: TreeNode, index?: number, allowCircularReferences?: boolean)

Adds the provided node as a child of this node. If the provided node already has a parent, it will first be removed from its previous parent.

You can specify an optional index at which to insert the child. If no index is provided, the child will be added to the end.

In addition, if the provided node is an ancestor to this node, this node will be removed from its parent before adding the node as a child. This prevents adding an ancestor as a child to create a loop, also known as a circular reference. You disable this protection by setting allowCircularReferences to true.

| Param | Description | | ------------------------- | ----------------------------------------------------------------------------------------------------- | | node | The node to add as a child. | | index | Optional. The index at which to insert the child. If undefined, the child will be added to the end. | | allowCircularReferences | Optional. Set to true to allow circular references. |

addChildData

addChildData(data: Record<string, any> = {}, index?: number): TreeNode

Creates a TreeNode with the data provided and adds it as a child. Returns the newly created TreeNode.

| Param | Description | | ------- | ---------------------------------------------------------------------------------------- | | data | The child data. A new node will be created from this data. | | index | The index at which to add the child. Pass undefined to add to the end of the children. |

| Returns | | --------------------------- | | The newly created TreeNode. |

getNodePath

getNodePath(): TreeNode[]

Returns an array containing all nodes in the tree leading to this one, starting with the root.

| Returns | | -------------------------------------------------------------------------------------- | | An array containing all nodes in the tree leading to this one, starting with the root. |

getSelectionPath

getSelectionPath(): number[]

Return an array of sibling index positions of all nodes leading to this one. This includes the root, which will always be the first item in the array with an index of 0, as root siblings are prohibited.

You can then use selectNode(selectionPath) to select this node at a later time. This is useful if your nodes do not have an ID and you want to reselect a node at a later time, or if your tree is large. It is much faster than a find() operation. The speed of selection is constant time, O(1), as you know exactly where to find the node.

For example, given a tree with the data:

{ id: 1, children: [
    { id: 2 },
    { id: 3, children: [
        { id: 4 },
        { id: 5 }
      ]
    }
  ]
}

The selection path for the node with id: 4 would be:

[0, 1, 0]

Selecting the node using this path is nearly instantaneous.

| Returns | | --------------------------------------------------------------------- | | An array of sibling index positions of all nodes leading to this one. |

selectNode

selectNode(selectionPath: number[]): TreeNode | undefined

Returns the TreeNode at the provided selection path, or undefined if the node at the provided selection path is not found.

A selection path is an array of sibling index positions of all nodes leading to the desired node. This includes the root, which will always be the first item in the array with an index of 0, as root siblings are prohibited.

This is useful if your nodes do not have an ID and you want to reselect a node at a later time, or if your tree is large. It is much faster than a find() operation. The speed of selection is constant time, O(1), as you know exactly where to find the node.

See getSelectionPath() for more.

| Param | Description | | --------------- | ----------------------------------------------------------------------------------------------- | | selectionPath | The selection path for the TreeNode as an array of sibling indexes leading to the desired node. |

| Returns | | --------------------------------------------------- | | The selected TreeNode, or undefined if not found. |

getChildren

getChildren(): TreeNode[]

Returns the children for this node.

| Returns | | --------------------------- | | The children for this node. |

hasChildren

hasChildren(): boolean

Returns true if this node has children. False otherwise.

| Returns | | ------------------------------------------------ | | True if this node has children. False otherwise. |

getFirstChild

getFirstChild(): TreeNode | undefined

Returns the first child in this node's list of children, or undefined if there are no children.

| Returns | | ----------------------------------------------------------------------------------------- | | The first child in this node's list of children, or undefined if there are no children. |

getLastChild

getLastChild(): TreeNode | undefined

Returns the last child in this node's list of children, or undefined if there are no children.

| Returns | | ---------------------------------------------------------------------------------------- | | The last child in this node's list of children, or undefined if there are no children. |

hasChild

hasChild(node: TreeNode)

Returns true if this node has the provided node in its direct list of children. False otherwise.

You can use isDescendant(node) to check for a child relationship along the entire tree hierarchy.

| Param | Description | | ------ | ----------------------- | | node | The node to search for. |

| Returns | | ---------------------------------------------------------------------------------------- | | True if this node has the provided node in its direct list of children. False otherwise. |

removeChild

removeChild(node: TreeNode): boolean

Removes the provided node from this node's list of children and sets the provided node's parent to undefined.

Returns true if the node was successfully removed. Returns false if the node was not found.

| Param | Description | | ------ | ------------------- | | node | The node to remove. |

| Returns | | -------------------------------------------------------- | | True if the node was removed. False if it was not found. |

removeParent

removeParent(): boolean

Removes this node from its parent and sets this node's parent to undefined.

Returns true if this node was successfully removed from its parent, false otherwise.

| Returns | | --------------------------------------------------------------- | | True if this node was removed from its parent, false otherwise. |

getSiblings

getSiblings(): TreeNode[]

Returns an array of all siblings for this node.

| Returns | | --------------------------------------- | | An array of all siblings for this node. |

getSiblingCount

getSiblingCount(): number

Returns the number of siblings this node has including itself.

| Returns | | ------------------------------------------------------ | | The number of siblings this node has including itself. |

isOnlyChild

isOnlyChild(): boolean

Returns true if this node is an only child (has no other siblings), false otherwise.

| Returns | | ---------------------------------------------------------------------------- | | True if this node is an only child (has no other siblings), false otherwise. |

getFirstSibling

getFirstSibling(): TreeNode

Returns the first sibling in this node's list of siblings.

| Returns | | -------------------------------------------------- | | The first sibling in this node's list of siblings. |

getLastSibling

getLastSibling(): TreeNode

Returns the last sibling in this node's list of siblings.

| Returns | | ------------------------------------------------- | | The last sibling in this node's list of siblings. |

getLeftSibling

getLeftSibling(): TreeNode | undefined

Returns the sibling to the left of this node, or undefined if there is none.

| Returns | | ---------------------------------------------------------------------- | | The sibling to the left of this node, or undefined if there is none. |

getRightSibling

getRightSibling(): TreeNode | undefined

Returns the sibling to the right of this node, or undefined if there is none.

| Returns | | ----------------------------------------------------------------------- | | The sibling to the right of this node, or undefined if there is none. |

addSiblingNode

addSiblingNode(node: TreeNode, index?: number)

Adds the provided node as a sibling to this node. You can specify an optional sibling index for the insertion, otherwise the sibling will be added to the end.

If you attempt to call this function at the root, an error will be thrown, as root nodes cannot have siblings. To prevent this, use isRoot() to check if you're at the root.

| Param | Description | | ------- | ---------------------------------------- | | node | The node to add as a sibling. | | index | Optional. The index for the new sibling. |

| Errors Thrown | | -------------------------------------- | | Throws an error if called at the root. |

addSiblingData

addSiblingData(data: Record<string, any> = {}, index?: number): TreeNode

Creates a TreeNode with the data provided and adds it as a sibling. Returns the newly created TreeNode.

If you attempt to call this function at the root, an error will be thrown, as root nodes cannot have siblings. To prevent this, use isRoot() to check if you're at the root.

| Param | Description | | ------- | ------------------------------------------------------------------------------------------ | | data | The sibling data. A new node will be created from this data. | | index | The index at which to add the sibling. Pass undefined to add to the end of the siblings. |

| Returns | | --------------------------- | | The newly created TreeNode. |

getIndex

getIndex(): number

Returns this node's index among its siblings.

Note: The root will always have an index of 0.

| Returns | | ------------------------------------- | | This node's index among its siblings. |

indexOfChild

indexOfChild(node: TreeNode): number

Returns the index of the provided node in this node's list of children, or -1 if it is not found.

| Param | Description | | ------ | --------------------------------------------------------------------- | | node | The node for which to find the index in this node's list of children. |

| Returns | | ------------------------------------------------------------------------------------------- | | The index of the provided node in this node's list of children, or -1 if it is not found. |

indexOfSibling

indexOfSibling(node: TreeNode): number

Returns the index of the provided node in this node's list of siblings, or -1 if it is not found.

| Param | Description | | ------ | --------------------------------------------------------------------- | | node | The node for which to find the index in this node's list of siblings. |

| Returns | | ------------------------------------------------------------------------------------------- | | The index of the provided node in this node's list of siblings, or -1 if it is not found. |

getParent

getParent(): TreeNode | undefined

Returns the parent of this node, or undefined if there is none.

| Returns | | --------------------------------------------------------- | | The parent of this node, or undefined if there is none. |

isParent

isParent(node: TreeNode)

Returns true if the provided node is this node's direct parent, false otherwise.

You can use isAncestor(node) to check for a parental relationship along the entire tree hierarchy.

| Param | Description | | ------ | ------------------ | | node | The node to check. |

| Returns | | ------------------------------------------------------------------------ | | True if the provided node is this node's direct parent, false otherwise. |

setParent

setParent(parent: TreeNode | undefined): void

Sets the provided node as the parent of this node. If parent is undefined, this node will be removed from its parent.

| Param | Description | | -------- | ---------------------------------- | | parent | The node to set as the new parent. |

getRoot

getRoot(): TreeNode

Returns the root node at the top of the tree hierarchy.

| Returns | | ----------------------------------------------- | | The root node at the top of the tree hierarchy. |

findFirst

findFirst(predicate: (node: TreeNode) => boolean, rightToLeft?: boolean): TreeNode | undefined

Searches the tree node and its children for the first node that passes the test defined by the matcher function provided.

The found node is returned. If not found, undefined is returned.

The find algorithm uses depth-first left-to-right preorder traversal by default. You can pass rightToLeft argument as true to use depth-first right-to-left preorder traversal instead.

| Param | Description | | ------------- | ----------------------------------------------------------------------------------------------------------------------------- | | predicate | A function used to match the node being searched for. This function is passed a node and returns true if the node is a match. | | rightToLeft | Optional. When true, searching will traverse the tree using depth-first right-to-left preorder traversal. |

| Returns | | -------------------------------------------- | | The found node, or undefined if not found. |

findAll

findAll(predicate: (node: TreeNode) => boolean, rightToLeft?: boolean): TreeNode[]

Searches the tree node and its children for all nodes that pass the test defined by the matcher function provided.

The found nodes are returned as an array of TreeNode.

The find algorithm uses depth-first left-to-right preorder traversal by default. You can pass rightToLeft argument as true to use depth-first right-to-left preorder traversal instead.

| Param | Description | | ------------- | ------------------------------------------------------------------------------------------------------------------------------ | | predicate | A function used to match the nodes being searched for. This function is passed a node and returns true if the node is a match. | | rightToLeft | Optional. When true, searching will traverse the tree using depth-first right-to-left preorder traversal. |

| Returns | | ------------------------------------------------ | | A TreeNode[] array containing all found nodes. |

findById

findById(id: any, idPropertyName = 'id', rightToLeft?: boolean): TreeNode | undefined

Finds and returns the node with the provided id (using === comparison), or returns undefined if not found.

Uses "id" as the property name by default, or you can provide the ID property name using the idPropertyName argument.

The find algorithm uses depth-first left-to-right preorder traversal by default. You can pass rightToLeft argument as true to use depth-first right-to-left preorder traversal instead.

| Param | Description | | ---------------- | --------------------------------------------------------------------------------------------------------- | | id | The node ID to search for. | | idPropertyName | Optional. The property name of the ID. Defaults as "id". | | rightToLeft | Optional. When true, searching will traverse the tree using depth-first right-to-left preorder traversal. |

| Returns | | ----------------------------------------------------------- | | The node with the provided id, or undefined if not found. |

walk

walk(visit: (node: TreeNode) => boolean | void, rightToLeft?: boolean): boolean

Walk the tree node and its children, calling the visit function on each node.

If the visit function returns true at any point, walking is aborted.

The walk algorithm uses depth-first left-to-right preorder traversal by default. You can pass rightToLeft argument as true to use depth-first right-to-left preorder traversal instead.

| Param | Description | | ------------- | --------------------------------------------------------------------------------------------------------------------- | | visit | A visit function called on every node traversed. If the visit function returns true at any point, walking is aborted. | | rightToLeft | Optional. When true, it will traverse the tree using depth-first right-to-left preorder traversal. |

| Returns | | --------------------------------------------------- | | True if the traversal was aborted, false otherwise. |

toObject

toObject(): Record<string, any>

Returns an object containing the tree node data including all nested children.

Note: Parents, if any, are not included.

| Returns | | ---------------------------------------------------------------------- | | An object containing the tree node data including all nested children. |

toJSON

toJSON(): string

Returns a JSON string of an object containing the tree node data including all nested children. Parents, if any, are not included.

This is accomplished by stringifying the tree node's toObject() value. As such, all data in the tree node must support JSON.stringify() or an error will be thrown.

@see You can use TreeNode.fromJSON() to construct a tree node from the resulting JSON output. @see If you'd like to clone the tree node, you can simply use clone() which converts to JSON and back to a TreeNode for you.

| Returns | | --------------------------------------------------------------------------------------- | | A JSON string of an object containing the tree node data including all nested children. |

| Errors Thrown | | ---------------------------------------------------------------------------------------- | | An error if the tree node data cannot be converted to a string using JSON.stringify(). |

clone

clone(): TreeNode

Returns a deep clone of the tree node, including all children. Parents, if any, are not included.

This is accomplished by stringifying the tree node's toObject() value, and then parsing the resulting JSON string to create an entirely new tree node. As such, all data in the tree node must support JSON.stringify() or an error will be thrown.

| Returns | | ------------------------------------------------------ | | A deep clone of the tree node, including all children. |

| Errors Thrown | | ------------------------------------------------------ | | An error if JSON.stringify() fails on the tree node. |

Static Functions

fromJSON

TreeNode.fromJSON(dataString: string, options: TreeNodeOptions = TreeNode.defaultTreeNodeOptions): TreeNode

Parses the provided data string, which contains an object with nested children, and creates a tree node from the resulting parsed object.

JSON example:

{
  "id": 1,
  "children": [{ "id": 2 }, { "id": 3, "children": [{ "id": 4 }, { "id": 5 }] }]
}

| Param | Description | | ------------ | --------------------------------------------------------------- | | dataString | The JSON data string containing an object with nested children. | | options | Optional. The options for the TreeNode. |

| Returns | | -------------------------------------------- | | A TreeNode constructed from the parsed JSON. |

| Errors Thrown | | ------------------------------- | | An error if JSON parsing fails. |

TypeScript

Type definitions have been included for TypeScript support.

Icon Attribution

Favicon by Twemoji.

Contributing

Open source software is awesome and so are you. 😎

Feel free to submit a pull request for bugs or additions, and make sure to update tests as appropriate. If you find a mistake in the docs, send a PR! Even the smallest changes help.

For major changes, open an issue first to discuss what you'd like to change.

⭐ Found It Helpful? Star It!

If you found this project helpful, let the community know by giving it a star: 👉⭐

License

See LICENSE.md.

Published

Vulnerabilities

Links

Maintainers

Keywords

Readme

Documentation

Overview

Demo - React-Based Tree Editor

Features include:

Donate

Table of Contents

Installation

Quick Start

TreeNode/Tree API

Class Functions

Constructor

getData

setData

getChildrenPropertyName

getOptions

hasParent

isRoot

equals

isDescendantOf

isAncestorOf

addChildNode

addChildData

getNodePath

getSelectionPath

selectNode

getChildren

hasChildren

getFirstChild

getLastChild

hasChild

removeChild

removeParent

getSiblings

getSiblingCount

isOnlyChild

getFirstSibling

getLastSibling

getLeftSibling

getRightSibling

addSiblingNode

addSiblingData

getIndex

indexOfChild

indexOfSibling

getParent

isParent

setParent

getRoot

findFirst

findAll

findById

walk

toObject

toJSON

clone

Static Functions

fromJSON

TypeScript

Icon Attribution

Contributing

⭐ Found It Helpful? Star It!

License