Go to Latest
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)

Properties

protected
_size: number
protected
root: BinarySearchNode<T> | null
readonly
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: BinarySearchNode<T>, direction: 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>): 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; }): BinarySearchTree<T>
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>