Binary Search Tree

A JavaScript Binary Search Tree data structure. This Binary Search Tree is not balanced, which makes inserting sorted values a lot slower than unsorted values.

Installation

Install @truck/binary-search-tree via npm:

$ npm install --save @truck/binary-search-tree

Methods

constructor(rootValue: any)

Builds a new Binary Search Tree with rootValue as the value at the root of the tree.

delete(value: any): boolean

O(n). Deletes the given value from the Binary Search Tree. The default === comparator is used to check whether values are equal.

delete(comparator: (value: any) => number): boolean

O(n). Deletes the value that matches comparator from the Binary Search Tree. The comparator must return either 1 to delete to the right, -1 to delete to the left, or 0 if the given value must be deleted.

insert(value: any): void

O(n). Inserts the given value into the Binary Search Tree. The default === comparator is used to check whether values are equal.

insert(value: any, comparator: (value: any) => number): void

O(n). Inserts the given value into the Binary Search Tree. The comparator must return either 1 to insert to the right or -1 to insert to the left.

search(value: any): BinarySearchTree

O(n). Searches for the given value in the Binary Search Tree. Returns a sub-Binary Search Tree if value is found, returns undefined otherwise.

search(comparator: (value: any) => number): BinarySearchTree

O(n). Searches the Binary Search Tree for a value using the given comparator. The comparator must return either 1 to search to the right, -1 to search to the left, or 0 when the value matches. Returns a sub-Binary Search Tree if value is found, returns undefined otherwise.

traverseBreadthFirst(callback: (binarySearchTree: BinarySearchTree) => void): void

O(n). Traverses the Binary Search Tree using Breadth-First traversal algorithm. Calls callback with the current BinarySearchTree on each iteration.

traverseDepthFirstInOrder(callback: (binarySearchTree: BinarySearchTree) => void): void

O(n). Traverses the Binary Search Tree using Depth-First (In-Order) traversal algorithm. Calls callback with the current BinarySearchTree on each iteration.

traverseDepthFirstPostOrder(callback: (binarySearchTree: BinarySearchTree) => void): void

O(n). Traverses the Binary Search Tree using Depth-First (Post-Order) traversal algorithm. Calls callback with the current BinarySearchTree on each iteration.

traverseDepthFirstPreOrder(callback: (binarySearchTree: BinarySearchTree) => void): void

O(n). Traverses the Binary Search Tree using Depth-First (Pre-Order) traversal algorithm. Calls callback with the current BinarySearchTree on each iteration.

Properties

.left: BinarySearchTree

A sub-Binary Search Tree that is the left child of the current. The value of .left will be smaller than the current .value. undefined if none exists.

.maximum: any

O(n). The maximum value in the Binary Search Tree.

.minimum: any

O(n). The minimum value in the Binary Search Tree.

.right: BinarySearchTree

A sub-Binary Search Tree that is the right child of the current. The value of .right will be larger than the current .value. undefined if none exists.

.value: any

The value inserted into the Binary Search Tree.

Examples

A Binary Search Tree is a standard class which can be instantiated with the new keyword:

import BinarySearchTree from '@truck/binary-search-tree';

const binarySearchTree = new BinarySearchTree(10);
// insert some values
binarySearchTree.insert(5);
binarySearchTree.insert(3);
binarySearchTree.insert(7);
binarySearchTree.insert(15);
binarySearchTree.insert(13);
binarySearchTree.insert(17);
// delete some values
binarySearchTree.delete(7); // true
binarySearchTree.delete(15); // true
binarySearchTree.delete(1000); // false
// The tree after insertion/deletion
//      10
//      / \
//    5    17
//   /    /
//  3    13

// search the tree for a value
const subTree = binarySearchTree.search(17); // tree of 17 with a left child of 13
// traverse the tree
const newArray = [];
binarySearchTree.traverseBreadthFirst(tree => newArray.push(tree.value)); // [10, 5, 7, 3, 13]

Testing

Use the following command to run all the tests described below together:

$ docker-compose run --rm app npm test

Commit messages

Commit messages are linted through the use of husky and @commitlint/cli using the @commitlint/config-conventional commit convention.

Please read through the AngularJS Git Commit Message Conventions to get a better understanding of how commit messages are formatted.

After doing an npm install the required git hooks wil be added automatically and commit messages will be linted automatically.

Linting

Linting is done using eslint using the eslint-config-airbnb-base configuration with very few alterations, all of which can be seen in the .eslintrc file in the root of this repository.

Linting can be run in isolation through the command:

$ docker-compose run --rm app npm run test:lint

Auditing

Auditing of dependencies is done through the npm audit command-line tool.

Auditing can be run in isolation through the command:

$ docker-compose run --rm app npm run test:vulnerabilities

Unit testing

Unit testing is done with jest. The test file for each file to be tested is to be placed alongside the file in testing and marked with the .test.js extension.

Unit testing can be run in isolation through the command:

$ docker-compose run --rm app npm run test:scripts

Contributing

Contributions are always welcome, just submit a PR to get the conversation going. Please make sure all tests pass before submitting a PR.

Releases

The moment a PR is merged into the master branch semantic-release will kick-off a new release, thus the importance of clear commit messages.