Module
Deno standard library
class BinarySearchTree
implements Iterable<T>
``````import { BinarySearchTree } from "https://deno.land/std@0.167.0/collections/binary_search_tree.ts";
``````

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.

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)

## Examples

Example 1

``````import {
ascend,
BinarySearchTree,
descend,
} from "https://deno.land/std@0.167.0/collections/binary_search_tree.ts";
import { assertEquals } from "https://deno.land/std@0.167.0/testing/asserts.ts";

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

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

T

## Properties

protected
_size: number
protected
root: BinarySearchNode<T> | null
size: number

The amount of values stored in the binary search tree.

## Methods

protected
findNode(value: T): BinarySearchNode<T> | null
protected
insertNode(Node: BinarySearchNode, value: T): BinarySearchNode<T> | null
protected
removeNode(value: T): BinarySearchNode<T> | null
protected
rotateNode(node, direction)

Removes all values from the binary search tree.

find(value: T): T | null

Returns node value if found in the binary search tree.

insert(value: T): boolean

Adds the value to the binary search tree if it does not already exist in it. Returns true if successful.

isEmpty(): boolean

Checks if the binary search tree is empty.

lnrValues(): IterableIterator<T>

Returns an iterator that uses in-order (LNR) tree traversal for retrieving values from the binary search tree.

lrnValues(): IterableIterator<T>

Returns an iterator that uses post-order (LRN) tree traversal for retrieving values from the binary search tree.

lvlValues(): IterableIterator<T>

Returns an iterator that uses level order tree traversal for retrieving values from the binary search tree.

max(): T | null

Returns the maximum value in the binary search tree or null if empty.

min(): T | null

Returns the minimum value in the binary search tree or null if empty.

nlrValues(): IterableIterator<T>

Returns an iterator that uses pre-order (NLR) tree traversal for retrieving values from the binary search tree.

remove(value: T): boolean

Removes node value from the binary search tree if found. Returns true if found and removed.

rnlValues(): IterableIterator<T>

Returns an iterator that uses reverse in-order (RNL) tree traversal for retrieving values from the binary search tree.

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

Returns an iterator that uses in-order (LNR) tree traversal for retrieving values from the binary search tree.

## Static Methods

from<T>(collection: ArrayLike<T> | Iterable<T> | BinarySearchTree<T>)

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

from<T>(collection: ArrayLike<T> | Iterable<T> | BinarySearchTree<T>, options: { compare?: (a: T, b: T) => number; })
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>