Plain Tree

What

Performant tree and node utility library.

Features

• Create trees
  • manually
  • from array
• Create nodes
  • manually
  • from array
  • from object
• Search
  • Find one
  • Find all
  • Some/Every
• Traverse (breath first and depth first)
• Nodes at height
• Nodes count
  • all
  • by height
• Width
• Height
• Depth
• Manipulate trees and nodes
• FlatMap
  • Into single array
  • Into array of arrays by height
• Convert to JSON
• ... and more (see below)

Why

Tree and node tools all in one handy, well tested package.

Install

npm i --save @lukeaus/plain-tree

Usage

import { Node, Tree } from '@lukeaus/plain-tree';

const rootNode = new Node('a');
const tree = new Tree(rootNode);
rootNode.addChild('b');

console.log(tree);
/*
Tree {
  root:
    Node {
      children: [ [Node] ],
      id: 'twsychkc3gdj7o30o3s3z6cb7vfpzb2xfgjl',
      parent: null,
      data: 'a'
    }
  }
*/

API

Creating a Tree

There are multiple ways to create a tree.

Manually via Declared Nodes

Assign nodes to variables then use node.addChild

import { Node, Tree } from '@lukeaus/plain-tree';

const rootNode = new Node('a');
const tree = new Tree(rootNode);
const nodeB = rootNode.addChild('b');
const nodeC = nodeB.addChild('c');

/* Tree Outline:
 * a
 *   - b
 *     - c
 */

Manually via Children

Add nodes by accessing the root node's children (and their children, and their children's children etc.)

import { Node, Tree } from '@lukeaus/plain-tree';

const rootNode = new Node('a');
const tree = new Tree(rootNode);
rootNode.addChild('b');
rootNode.children[0].addChild('c');

/* Tree Outline:
 * a
 *   - b
 *     - c
 */

Create a Tree From a Flat Array of Objects

createTreeFromFlatArray(arr, ?opts)

Return: Tree instance

arr

Type: Array

Description: An array of objects. Object should have:

• id
• parent id (optional)
• children (optional)
• some other properties (all other properties will be converted to an object and will be available on node's data property )

opts

Type: Object

Description: Options for creation of tree

| Parameter | Type | Default | Description | | ----------- | ------ | ---------- | ------------------------------------------------- | | idKey | String | 'id' | Object's property whose value is each node's id | | parentIdKey | String | 'parentId' | Object's property whose value is parent node's id | | childrenKey | String | 'children' | Object's property whose value is child objects |

Example

import { createTreeFromFlatArray } from '@lukeaus/plain-tree';

const arr = [
  {
    id: 'sports',
    name: 'Sports',
    parentId: null
  },
  {
    id: 'ball',
    name: 'Ball',
    parentId: 'sports'
  },
  {
    id: 'non-ball',
    name: 'Non Ball',
    parentId: 'sports'
  },
  {
    id: 'tennis',
    name: 'Tennis',
    parentId: 'ball'
  }
];

createTreeFromFlatArray(arr);

/* Tree Outline:
 * Sports
 *   - Ball
 *     - Tennis
 *   - Non Ball
 */

Create a Tree From an Array of Nested Objects

createTreeFromTreeArray(arr, ?opts)

Return: Tree instance

arr

Type: Array

Description: An array of objects. Object should have:

• id
• parent id (optional)
• children (optional)
• some other properties (all other properties will be converted to an object and will be available on node's data property )

opts

Type: Object

Description: Options for creation of tree

| Parameter | Type | Default | Description | | ----------- | ------ | ---------- | ------------------------------------------------- | | idKey | String | 'id' | Object's property whose value is each node's id | | parentIdKey | String | 'parentId' | Object's property whose value is parent node's id | | childrenKey | String | 'children' | Object's property whose value is child objects |

Example

import { createTreeFromTreeArray } from '@lukeaus/plain-tree';

const arr = [
  {
    id: 'sports',
    name: 'Sports',
    parentId: null,
    children: [
      {
        id: 'ball',
        name: 'Ball',
        parentId: 'sports',
        children: [
          {
            id: 'tennis',
            name: 'Tennis',
            parentId: 'ball',
            children: []
          }
        ]
      },
      {
        id: 'non-ball',
        name: 'Non Ball',
        parentId: 'sports',
        children: []
      }
    ]
  }
];
createTreeFromTreeArray(arr);

/* Tree Outline:
 * Sports
 *   - Ball
 *     - Tennis
 *   - Non Ball
 */

Adding Additional Nodes to Existing Tree

Manually via Declared Nodes

Assign nodes to variables then use node.addChild

import { Node } from '@lukeaus/plain-tree';

// find/use an existing node
const nodeB = node.addChild('b');
const nodeC = nodeB.addChild('c');

Manually via Children

Add nodes by accessinga node's children (and their children, and their children's children etc.)

import { Node, Tree } from '@lukeaus/plain-tree';

// find/use an existing node
node.addChild('b');
node.children[0].addChild('c');

From Tree Array

createNodes(arr, ?parentNode, ?opts)

Create nodes from an array of nested objects

Return: void

arr

Type: Array

Description: An array of objects. Object should have:

• id
• parent id (optional)
• children (optional)
• some other properties (all other properties will be converted to an object and will be available on node's data property )

parentNode

Type: Node | null

Description: Parent node for nodes in array

opts

Type: Object

Description: Options for creation of tree

| Parameter | Type | Default | Description | | ----------- | ------ | ---------- | ------------------------------------------------- | | idKey | String | 'id' | Object's property whose value is each node's id | | parentIdKey | String | 'parentId' | Object's property whose value is parent node's id | | childrenKey | String | 'children' | Object's property whose value is child objects |

Example

import { createNodes } from '@lukeaus/plain-tree';

const parentNode = new Node('a'));
const arr: any = [
  {
    id: 'sports',
    name: 'Sports',
    parentId: null,
    children: [
      {
        id: 'ball',
        name: 'Ball',
        parentId: 'sports',
        children: [
          {
            id: 'tennis',
            name: 'Tennis',
            parentId: 'ball',
            children: []
          }
        ]
      },
      {
        id: 'non-ball',
        name: 'Non Ball',
        parentId: 'sports',
        children: []
      }
    ]
  }
];

createNodes(arr, parentNode);

Tree

constructor(root)

Creates and returns the tree

root

Type: Node or null

Default: null

Description: The tree root

traverseBreathFirst(fn)

Traverse every node in the tree breath first

Return: void

fn

Type: Function

| Parameter | Type | Description | | --------- | ------------ | -------------- | | 1 | Node | null | A Node or null |

traverseDepthFirst(fn)

Traverse every node in the tree depth first

Return: void

fn

Type: Function

| Parameter | Type | Description | | --------- | ------------ | -------------- | | 1 | Node | null | A Node or null |

findOneBreathFirst(fn)

Traverse nodes in the tree breath first. Returns the first matching Node or null.

Return: Node | null

fn

Type: Function

| Parameter | Type | Description | | --------- | ------------ | -------------- | | 1 | Node | null | A Node or null |

findOneDepthFirst(fn)

Traverse nodes in the tree depth first. Returns the first matching Node or null.

Return: Node | null

fn

Type: Function

| Parameter | Type | Description | | --------- | ------------ | -------------- | | 1 | Node | null | A Node or null |

findAllBreathFirst(fn)

Traverse nodes in the tree breath first. Returns an array containing all matching Nodes.

Return: Array

fn

Type: Function

| Parameter | Type | Description | | --------- | ------------ | -------------- | | 1 | Node | null | A Node or null |

findAllDepthFirst(fn)

Traverse nodes in the tree depth first. Returns an array containing all matching Nodes.

Return: Array

fn

Type: Function

| Parameter | Type | Description | | --------- | ------------ | -------------- | | 1 | Node | null | A Node or null |

someBreathFirst(fn)

Traverse nodes in the tree breath first. Return true if a single node is truthy for fn, else return false. Breaks on first truthy for performance.

Return: Boolean

fn

Type: Function

| Parameter | Type | Description | | --------- | ------------ | -------------- | | 1 | Node | null | A Node or null |

someDepthFirst(fn)

Traverse nodes in the tree depth first. Return true if a single node is truthy for fn, else return false. Breaks on first truthy for performance.

Return: Boolean

fn

Type: Function

| Parameter | Type | Description | | --------- | ------------ | -------------- | | 1 | Node | null | A Node or null |

everyBreathFirst(fn)

Traverse every node in the tree breath first. Return true if every node is truthy for fn, else return false. Breaks on first falsey for performance.

Return: Boolean

fn

Type: Function

| Parameter | Type | Description | | --------- | ------------ | -------------- | | 1 | Node | null | A Node or null |

everyDepthFirst(fn)

Traverse every node in the tree depth first. Return true if every node is truthy for fn, else return false. Breaks on first falsey for performance.

Return: Boolean

fn

Type: Function

| Parameter | Type | Description | | --------- | ------------ | -------------- | | 1 | Node | null | A Node or null |

flatMap(?fn)

Traverse every node in the tree breath first and flatten the tree into a single array.

Return: Array<Node|null>

fn

Type: Function

Default: null (if null, flatten will push the node into the array)

| Parameter | Type | Description | | --------- | ------------ | -------------- | | 1 | Node | null | A Node or null |

flattenData()

Traverse every node in the tree breath first and flatten the tree into a single array. Extract the 'data' property of each Node (if node is not null) and return an array of any. This is a helper method which is essentially flatten(nodeData);

Return: Array

flattenByHeight(?fn)

Traverse every node in the tree breath first and flatten the tree into an array of arrays, where each array is for each height level in the tree.

Return: Array<Array>

fn

Type: Function

Default: null (if null, flatten will push the node into the array)

| Parameter | Type | Description | | --------- | ------------ | -------------- | | 1 | Node | null | A Node or null |

Example

import { Node, Tree } from '@lukeaus/plain-tree';

const nodeA = new Node('a');
const tree = new Tree(nodeA);
nodeA.addChild('b');
const nodeC = nodeA.addChild('c');
nodeC.addChild('d');

tree.flattenByHeight(nodeData);
/* Output
[['a'], ['b', 'c'], ['d']];
*/

flattenDataByHeight()

Traverse every node in the tree breath first and flatten the tree into an array of arrays, where each array is for each height level in the tree. Extract the 'data' property of each Node (if node is not null). This is a helper method which is essentially flattenByHeight(nodeData);

Return: Array<Array>

widthsByHeight()

Return the width of children at each height

Example

import { Tree, Node, hasChildren, nodeData } from '@lukeaus/plain-tree';

const nodeA = new Node('a');
const tree = new Tree(nodeA);
nodeA.addChild('b');
nodeA.addChild('c');
nodeA.children[0].addChild('d');

tree.widthsByHeight(); // [1, 2 , 1]

nodesAtHeight(number)

Return all the nodes at that height (root is at height 0)

Return: Array<Node|null>

number

Type: Number

Description: Number indicating the tree height at which you want to obtain all nodes

maxWidth()

Return the maximum width of any height level in the tree

Return: Number

height()

Return the height of the tree. Equivalent to height of root node. A tree with only root will be height 0.

Return: Number

countNodes()

Return the number of nodes in a tree. A tree with root of null will return 1.

Return: Number

toJson()

Stringify the tree. Due to circular dependencies, the parent property is dropped and replaced with property parentId (type String | null) which is the id of the parent (if it exists) else null.

If root is null, an empty string is returned.

Return: String

Node

constructor(data, ?opts)

Create a new Node instance

Return: Node

data

The node's data (excluding interal node properties)

Type: any

parent

The node's parent node (if it exists, otherwise null)

Type: Node | null

opts

| Parameter | Type | Description | | --------- | ------------ | ----------- | | id | String | id | | parent | Node | null | parent node |

addChild(data)

Add a child to this node. Return the newly created child Node instance.

Return: Node

data

Type: any

removeChildren(fn)

Remove all children where fn returns truthy. Use this where data is complex (e.g. data is an Object or Array). Returns removed children.

Return: Array

fn

| Parameter | Type | Description | | --------- | ------------ | --------------------- | | 1 | Node | null | A child Node instance |

removeChildrenByData(data)

Remove all children where child's data property matches data. Use removeChildren where data is complex (e.g. data is an Object or Array). Returns removed children.

Return: Array

data

Type: any

removeChildrenById(id)

Remove all children where child's id property matches id. Use removeChildren where data is complex (e.g. data is an Object or Array). Returns removed children.

Return: Array

id

Type: String

isLeaf()

Returns a Boolean. False if this Node instance has children. True if it does have children.

Return: Boolean

hasChildren()

Returns a Boolean. True if this Node instance has children. False if it does have children.

Return: Boolean

widthsByHeight()

Return the width of children at each height

Example

import { Tree, Node, hasChildren, nodeData } from '@lukeaus/plain-tree';

const nodeA = new Node('a');
nodeA.addChild('b');
nodeA.addChild('c');
nodeA.children[0].addChild('d');

nodeA.widthsByHeight(); // [1, 2 , 1]

height()

Return the height of the node.

Return: Number

depth()

Return the depth of the node.

Return: Number

flattenByHeight(?fn)

Traverse node and its children breath first and flatten into an array of arrays, where each array is for each height level (with this node at height 0).

Return: Array<Array>

fn

Type: Function

Default: null (if null, flatten will push the node into the array)

| Parameter | Type | Description | | --------- | ------------ | -------------- | | 1 | Node | null | A Node or null |

Example

import { Node } from '@lukeaus/plain-tree';

const nodeA = new Node('a');
nodeA.addChild('b');
const nodeC = nodeA.addChild('c');
nodeC.addChild('d');

nodeA.flattenByHeight(nodeData);
/* Output
[['a'], ['b', 'c'], ['d']];
*/

toJson()

Stringify the node. Due to circular dependencies, parent property is dropped and replaced with parentId (type String | null).

Return: String

Utils

nodeData(any)

Return a nodes data. Safe function to protect against accessing data property on null.

Return: any

any

Type: any

nodesData(any)

Convenience method to return all node data on an array of nodes.

Return: Array

any

Type: Array

hasChildren(any)

Return true if node has children. Return false if no children.

Return: boolean

any

Type: any

Contributing

Contributions are welcomed. How to make a contribution:

• Create an issue on Github
• Fork project
• Make changes
• Test changes npm run test
• Use npm run commit to commit
• Create a pull request