Skip to main content
Deno 2 is finally here 🎉️
Learn more
Module

std/collections/binary_search_tree.ts>BinarySearchTree

Deno standard library
denoland/deno_std
Go to Latest
The Standard Library has been moved to JSR. See the blog post for details.
class BinarySearchTree
implements Iterable<T>
import { BinarySearchTree } from "https://deno.land/std@0.159.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.

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)
clear()

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>