BinarySearchTree

import { BinarySearchTree } from "jsr:@ende/data-structures";

class

class BinarySearchTree<T> implements Iterable<T>

An unbalanced binary search tree. The values are in ascending order by default, using JavaScript's built-in comparison operators to sort the values.

For performance, it's recommended that you use a self-balancing binary search tree instead of this one unless you are extending this to create a self-balancing tree. See RedBlackTree for an example of how BinarySearchTree can be extended to create a self-balancing binary search tree.

The following bounds are for a tree of n values, or an input collection of n values for from(). Traversal bounds cover consuming the entire iterator; comparison and mapping functions are assumed to take O(1).

Method	Average Case	Worst Case
find(value)	O(log n)	O(n)
insert(value)	O(log n)	O(n)
remove(value)	O(log n)	O(n)
min()	O(log n)	O(n)
max()	O(log n)	O(n)
size	O(1)	O(1)
isEmpty()	O(1)	O(1)
clear()	O(1)	O(1)
lnrValues()	O(n)	O(n)
rnlValues()	O(n)	O(n)
nlrValues()	O(n)	O(n)
lrnValues()	O(n)	O(n)
lvlValues()	O(n)	O(n)
Symbol.iterator	O(n)	O(n)
BinarySearchTree()	O(1)	O(1)
BinarySearchTree.from()	O(n log n)	O(n²)

BinarySearchTree.from takes O(n) when copying a BinarySearchTree without a compare or map option, since it clones the tree structure directly instead of reinserting the values.

Example: Usage

import {
  BinarySearchTree,
  ascend,
  descend,
} from "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const values = [3, 10, 13, 4, 6, 7, 1, 14];
const tree = new BinarySearchTree<number>();
values.forEach((value) => tree.insert(value));
assertEquals([...tree], [1, 3, 4, 6, 7, 10, 13, 14]);
assertEquals(tree.min(), 1);
assertEquals(tree.max(), 14);
assertEquals(tree.find(42), null);
assertEquals(tree.find(7), 7);
assertEquals(tree.remove(42), false);
assertEquals(tree.remove(7), true);
assertEquals([...tree], [1, 3, 4, 6, 10, 13, 14]);

const invertedTree = new BinarySearchTree<number>(descend);
values.forEach((value) => invertedTree.insert(value));
assertEquals([...invertedTree], [14, 13, 10, 7, 6, 4, 3, 1]);
assertEquals(invertedTree.min(), 14);
assertEquals(invertedTree.max(), 1);
assertEquals(invertedTree.find(42), null);
assertEquals(invertedTree.find(7), 7);
assertEquals(invertedTree.remove(42), false);
assertEquals(invertedTree.remove(7), true);
assertEquals([...invertedTree], [14, 13, 10, 6, 4, 3, 1]);

const words = new BinarySearchTree<string>((a, b) =>
  ascend(a.length, b.length) || ascend(a, b)
);
["truck", "car", "helicopter", "tank", "train", "suv", "semi", "van"]
  .forEach((value) => words.insert(value));
assertEquals([...words], [
  "car",
  "suv",
  "van",
  "semi",
  "tank",
  "train",
  "truck",
  "helicopter",
]);
assertEquals(words.min(), "car");
assertEquals(words.max(), "helicopter");
assertEquals(words.find("scooter"), null);
assertEquals(words.find("tank"), "tank");
assertEquals(words.remove("scooter"), false);
assertEquals(words.remove("tank"), true);
assertEquals([...words], [
  "car",
  "suv",
  "van",
  "semi",
  "train",
  "truck",
  "helicopter",
]);

Constructors

`constructor`

new BinarySearchTree(compare: (a: T, b: T) => number = ascend)

Construct an empty binary search tree.

To create a binary search tree from an array like, an iterable object, or an existing binary search tree, use the BinarySearchTree.from method.

compare: (a: T, b: T) => number = ascend: A custom comparison function to sort the values in the tree. By default, the values are sorted in ascending order.

Static methods

`from`

static from<T>(collection: ArrayLike<T> | Iterable<T> | BinarySearchTree<T>, options?: { compare?: (a: T, b: T) => number }): BinarySearchTree<T>

Creates a new binary search tree from an array like, an iterable object, or an existing binary search tree.

A custom comparison function can be provided to sort the values in a specific order. By default, the values are sorted in ascending order, unless a BinarySearchTree is passed, in which case the comparison function is copied from the input tree.

collection: ArrayLike<T> | Iterable<T> | BinarySearchTree<T>: An array like, an iterable, or existing binary search tree.
options?: { compare?: (a: T, b: T) => number }: An optional options object to customize the comparison function.

Returns

A new binary search tree created from the passed collection.

Example: Creating a binary search tree from an array like

import { BinarySearchTree } from "@ende/data-structures";

const tree = BinarySearchTree.from<number>([42, 43, 41]);

Example: Creating a binary search tree from an iterable object

import { BinarySearchTree } from "@ende/data-structures";

const tree = BinarySearchTree.from<number>((function*() {
  yield 42;
  yield 43;
  yield 41;
})());

Example: Creating a binary search tree from an existing binary search tree

import { BinarySearchTree } from "@ende/data-structures";

const tree = BinarySearchTree.from<number>([42, 43, 41]);
const copy = BinarySearchTree.from(tree);

Example: Creating a binary search tree from an array like with a custom comparison function

import { BinarySearchTree, descend } from "@ende/data-structures";

const tree = BinarySearchTree.from<number>(
  [42, 43, 41],
  { compare: descend }
);

static from<T, U, V = undefined>(collection: ArrayLike<T> | Iterable<T> | BinarySearchTree<T>, options: { compare?: (a: U, b: U) => number; map: (value: T, index: number) => U; thisArg?: V }): BinarySearchTree<U>

Create a new binary search tree from an array like, an iterable object, or an existing binary search tree.

A custom mapping function can be provided to transform the values before inserting them into the tree.

A custom comparison function can be provided to sort the values in a specific order. A custom mapping function can be provided to transform the values before inserting them into the tree. By default, the values are sorted in ascending order, unless a BinarySearchTree is passed, in which case the comparison function is copied from the input tree. The comparison operator is used to sort the values in the tree after mapping the values.

collection: ArrayLike<T> | Iterable<T> | BinarySearchTree<T>: An array like, an iterable, or existing binary search tree.
options: { compare?: (a: U, b: U) => number; map: (value: T, index: number) => U; thisArg?: V }: The options object to customize the mapping and comparison functions. The thisArg property can be used to set the this value when calling the mapping function.

Returns

A new binary search tree containing the mapped values from the passed collection.

Example: Creating a binary search tree from an array like with a custom mapping function

import { BinarySearchTree } from "@ende/data-structures";

const tree = BinarySearchTree.from<number, string>(
  [42, 43, 41],
  { map: (value) => value.toString() }
);

static from<T, U, V>(collection: ArrayLike<T> | Iterable<T> | BinarySearchTree<T>, options?: { compare?: (a: U, b: U) => number; map?: (value: T, index: number) => U; thisArg?: V }): BinarySearchTree<U>

Methods

`size`

get size(): number

The count of values stored in the binary search tree.

The complexity of this operation is O(1).

Returns

The count of values stored in the binary search tree.

Example: Getting the size of the tree

import { BinarySearchTree } from "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const tree = BinarySearchTree.from<number>([42, 43, 41]);

assertEquals(tree.size, 3);

`insert`

insert(value: T): boolean

Add a value to the binary search tree if it does not already exist in the tree.

The complexity of this operation is on average O(log n), where n is the number of values in the tree. In the worst case, the complexity is O(n).

value: T: The value to insert into the binary search tree.

Returns

true if the value was inserted, false if the value already exists in the tree.

Example: Inserting values into the tree

import { BinarySearchTree } from "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const tree = new BinarySearchTree<number>();

assertEquals(tree.insert(42), true);
assertEquals(tree.insert(42), false);

`remove`

remove(value: T): boolean

Remove a value from the binary search tree if it exists in the tree.

The complexity of this operation is on average O(log n), where n is the number of values in the tree. In the worst case, the complexity is O(n).

value: T: The value to remove from the binary search tree.

Returns

true if the value was found and removed, false if the value was not found in the tree.

Example: Removing values from the tree

import { BinarySearchTree } from "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const tree = BinarySearchTree.from<number>([42]);

assertEquals(tree.remove(42), true);
assertEquals(tree.remove(42), false);

`find`

find(value: T): T | null

Check if a value exists in the binary search tree.

The complexity of this operation depends on the underlying structure of the tree. Refer to the documentation of the structure itself for more details.

value: T: The value to search for in the binary search tree.

Returns

The value if it was found, or null if not found.

Example: Finding values in the tree

import { BinarySearchTree } from "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const tree = BinarySearchTree.from<number>([42]);

assertEquals(tree.find(42), 42);
assertEquals(tree.find(43), null);

`min`

min(): T | null

Retrieve the lowest (left most) value in the binary search tree, or null if the tree is empty.

The complexity of this operation depends on the underlying structure of the tree. Refer to the documentation of the structure itself for more details.

Returns

The minimum value in the binary search tree, or null if the tree is empty.

Example: Finding the minimum value in the tree

import { BinarySearchTree } from "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const tree = BinarySearchTree.from<number>([42, 43, 41]);

assertEquals(tree.min(), 41);

`max`

max(): T | null

Retrieve the highest (right most) value in the binary search tree, or null if the tree is empty.

The complexity of this operation depends on the underlying structure of the tree. Refer to the documentation of the structure itself for more details.

Returns

The maximum value in the binary search tree, or null if the tree is empty.

Example: Finding the maximum value in the tree

import { BinarySearchTree } from "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const tree = BinarySearchTree.from<number>([42, 43, 41]);

assertEquals(tree.max(), 43);

`clear`

clear(): void

Remove all values from the binary search tree.

The complexity of this operation is O(1).

Example: Clearing the tree

import { BinarySearchTree } from "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const tree = BinarySearchTree.from<number>([42, 43, 41]);
tree.clear();

assertEquals(tree.size, 0);
assertEquals(tree.find(42), null);

`isEmpty`

isEmpty(): boolean

Check if the binary search tree is empty.

The complexity of this operation is O(1).

Returns

true if the binary search tree is empty, false otherwise.

Example: Checking if the tree is empty

import { BinarySearchTree } from "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const tree = new BinarySearchTree<number>();

assertEquals(tree.isEmpty(), true);

tree.insert(42);

assertEquals(tree.isEmpty(), false);

`lnrValues`

lnrValues(): IterableIterator<T>

Create an iterator over this tree that traverses the tree in-order (LNR, Left-Node-Right).

Returns

An iterator that traverses the tree in-order (LNR).

Example: Using the in-order LNR iterator

import { BinarySearchTree } from "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const tree = BinarySearchTree.from([4, 1, 2, 5, 3]);

assertEquals([...tree.lnrValues()], [1, 2, 3, 4, 5]);

`rnlValues`

rnlValues(): IterableIterator<T>

Create an iterator over this tree that traverses the tree in reverse in-order (RNL, Right-Node-Left).

Returns

An iterator that traverses the tree in reverse in-order (RNL).

Example: Using the reverse in-order RNL iterator

import { BinarySearchTree } from "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const tree = BinarySearchTree.from([4, 1, 2, 5, 3]);
[...tree.rnlValues()] // 5, 4, 3, 2, 1

`nlrValues`

nlrValues(): IterableIterator<T>

Create an iterator over this tree that traverses the tree in pre-order (NLR, Node-Left-Right).

Returns

An iterator that traverses the tree in pre-order (NLR).

Example: Using the pre-order NLR iterator

import { BinarySearchTree } from "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const tree = BinarySearchTree.from([4, 1, 2, 5, 3]);

assertEquals([...tree.nlrValues()], [4, 1, 2, 3, 5]);

`lrnValues`

lrnValues(): IterableIterator<T>

Create an iterator over this tree that traverses the tree in post-order (LRN, Left-Right-Node).

Returns

An iterator that traverses the tree in post-order (LRN).

Example: Using the post-order LRN iterator

import { BinarySearchTree } from "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const tree = BinarySearchTree.from([4, 1, 2, 5, 3]);

assertEquals([...tree.lrnValues()], [3, 2, 1, 5, 4]);

`lvlValues`

lvlValues(): IterableIterator<T>

Create an iterator over this tree that traverses the tree in level-order (BFS, Breadth-First Search).

Returns

An iterator that traverses the tree in level-order (BFS).

Example: Using the level-order BFS iterator

import { BinarySearchTree } from "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const tree = BinarySearchTree.from([4, 1, 2, 5, 3]);

assertEquals([...tree.lvlValues()], [4, 1, 5, 2, 3]);

`[Symbol.iterator]`

[Symbol.iterator](): IterableIterator<T>

Create an iterator over this tree that traverses the tree in-order (LNR, Left-Node-Right).

Returns

An iterator that traverses the tree in-order (LNR).

Example: Using the in-order iterator

import { BinarySearchTree } from "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const tree = BinarySearchTree.from([4, 1, 2, 5, 3]);

assertEquals([...tree], [1, 2, 3, 4, 5]);

See BinarySearchTree.prototype.lnrValues.

Source