Class BinarySearchTree<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.

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)

Example: Usage

import {
  BinarySearchTree,
  ascend,
  descend,
} from "@std/data-structures";
import { assertEquals } from "@std/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",
]);

Typeparam

T The type of the values stored in the binary search tree.

Type Parameters

  • T
Implements
  • Iterable<T>
Hierarchy

Constructors

constructor

Accessors

size

Methods

[iterator] clear find insert isEmpty lnrValues lrnValues lvlValues max min nlrValues remove rnlValues from

Constructors

constructor

  • new BinarySearchTree<T>(compare?): BinarySearchTree<T>

  • 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.

    Type Parameters

    • T

    Parameters

    • 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.

        • (a, b): number

        • Parameters

          Returns number

    Returns BinarySearchTree<T>

Accessors

size

  • get size(): number

  • The count of values stored in the binary search tree.

    The complexity of this operation is O(1).

    Returns number

    The count of values stored in the binary search tree.

    Example: Getting the size of the tree

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

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

    assertEquals(tree.size, 3);

Methods

[iterator]

  • [iterator](): IterableIterator<T, any, any>

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

    Returns IterableIterator<T, any, any>

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

    Example: Using the in-order iterator

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

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

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

    See BinarySearchTree.prototype.lnrValues.

clear

  • clear(): void

  • Remove all values from the binary search tree.

    The complexity of this operation is O(1).

    Returns void

    Example: Clearing the tree

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

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

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

find

  • find(value): null | T

  • 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.

    Parameters

    • value: T

      The value to search for in the binary search tree.

    Returns null | T

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

    Example: Finding values in the tree

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

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

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

insert

  • insert(value): 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).

    Parameters

    • value: T

      The value to insert into the binary search tree.

    Returns boolean

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

    Example: Inserting values into the tree

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

    const tree = new BinarySearchTree<number>();

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

isEmpty

  • isEmpty(): boolean

  • Check if the binary search tree is empty.

    The complexity of this operation is O(1).

    Returns boolean

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

    Example: Checking if the tree is empty

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

    const tree = new BinarySearchTree<number>();

    assertEquals(tree.isEmpty(), true);

    tree.insert(42);

    assertEquals(tree.isEmpty(), false);

lnrValues

  • lnrValues(): IterableIterator<T, any, any>

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

    Returns IterableIterator<T, any, any>

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

    Example: Using the in-order LNR iterator

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

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

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

lrnValues

  • lrnValues(): IterableIterator<T, any, any>

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

    Returns IterableIterator<T, any, any>

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

    Example: Using the post-order LRN iterator

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

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

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

lvlValues

  • lvlValues(): IterableIterator<T, any, any>

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

    Returns IterableIterator<T, any, any>

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

    Example: Using the level-order BFS iterator

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

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

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

max

  • max(): null | T

  • 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 null | T

    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 "@std/data-structures";
    import { assertEquals } from "@std/assert";

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

    assertEquals(tree.max(), 43);

min

  • min(): null | T

  • 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 null | T

    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 "@std/data-structures";
    import { assertEquals } from "@std/assert";

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

    assertEquals(tree.min(), 41);

nlrValues

  • nlrValues(): IterableIterator<T, any, any>

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

    Returns IterableIterator<T, any, any>

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

    Example: Using the pre-order NLR iterator

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

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

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

remove

  • remove(value): 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).

    Parameters

    • value: T

      The value to remove from the binary search tree.

    Returns boolean

    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 "@std/data-structures";
    import { assertEquals } from "@std/assert";

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

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

rnlValues

  • rnlValues(): IterableIterator<T, any, any>

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

    Returns IterableIterator<T, any, any>

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

    Example: Using the reverse in-order RNL iterator

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

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

Staticfrom

  • from<T>(collection, options?): 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.

    Type Parameters

    • T

    Parameters

    • collection: ArrayLike<T> | Iterable<T, any, any> | BinarySearchTree<T>

      An array like, an iterable, or existing binary search tree.

    • Optionaloptions: {
          compare?: ((a: T, b: T) => number);
      }

      An optional options object to customize the comparison function.

      • Optionalcompare?: ((a: T, b: T) => number)
          • (a, b): number

          • Parameters

            Returns number

    Returns BinarySearchTree<T>

    A new binary search tree created from the passed collection.

    Example: Creating a binary search tree from an iterable object

    import { BinarySearchTree } from "@std/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 "@std/data-structures";

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

    Typeparam

    T The type of the values stored in the binary search tree.

  • from<T, U, V>(collection, options): 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.

    Type Parameters

    • T
    • U
    • V = undefined

    Parameters

    • collection: ArrayLike<T> | Iterable<T, any, any> | 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.

      • Optionalcompare?: ((a: U, b: U) => number)
          • (a, b): number

          • Parameters

            Returns number

      • map: ((value: T, index: number) => U)
          • (value, index): U

          • Parameters

            • value: T
            • index: number

            Returns U

      • OptionalthisArg?: V

    Returns BinarySearchTree<U>

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

    Typeparam

    T The type of the values in the passed collection.

    Typeparam

    U The type of the values stored in the binary search tree.

    Typeparam

    V The type of the this value when calling the mapping function. Defaults to undefined.

Settings

Member Visibility

On This Page

Constructors
Accessors
Methods