BST

Class: BST<K, V, R>

Defined in: data-structures/binary-tree/bst.ts:327

Represents a Binary Search Tree (BST). Keys are ordered, allowing for faster search operations compared to a standard Binary Tree.

Examples

// BST delete and search after deletion
 const bst = new BST<number>([11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5]);

    // Delete a leaf node
    bst.delete(1);
    console.log(bst.has(1)); // false;

    // Delete a node with one child
    bst.delete(2);
    console.log(bst.has(2)); // false;

    // Delete a node with two children
    bst.delete(3);
    console.log(bst.has(3)); // false;

    // Size decreases with each deletion
    console.log(bst.size); // 13;

    // Other nodes remain searchable
    console.log(bst.has(11)); // true;
    console.log(bst.has(15)); // true;

// Merge 3 sorted datasets
 const dataset1 = new BST<number, string>([
      [1, 'A'],
      [7, 'G']
    ]);
    const dataset2 = [
      [2, 'B'],
      [6, 'F']
    ];
    const dataset3 = new BST<number, string>([
      [3, 'C'],
      [5, 'E'],
      [4, 'D']
    ]);

    // Merge datasets into a single BinarySearchTree
    const merged = new BST<number, string>(dataset1);
    merged.setMany(dataset2);
    merged.merge(dataset3);

    // Verify merged dataset is in sorted order
    console.log([...merged.values()]); // ['A', 'B', 'C', 'D', 'E', 'F', 'G'];

// BST with custom objects for expression evaluation
 interface Expression {
      id: number;
      operator: string;
      precedence: number;
    }

    // BST efficiently stores and retrieves operators by precedence
    const operatorTree = new BST<number, Expression>(
      [
        [1, { id: 1, operator: '+', precedence: 1 }],
        [2, { id: 2, operator: '*', precedence: 2 }],
        [3, { id: 3, operator: '/', precedence: 2 }],
        [4, { id: 4, operator: '-', precedence: 1 }],
        [5, { id: 5, operator: '^', precedence: 3 }]
      ],
      { isMapMode: false }
    );

    console.log(operatorTree.size); // 5;

    // Quick lookup of operators
    const mult = operatorTree.get(2);
    console.log(mult?.operator); // '*';
    console.log(mult?.precedence); // 2;

    // Check if operator exists
    console.log(operatorTree.has(5)); // true;
    console.log(operatorTree.has(99)); // false;

    // Retrieve operator by precedence level
    const expNode = operatorTree.getNode(3);
    console.log(expNode?.key); // 3;
    console.log(expNode?.value?.precedence); // 2;

    // Delete operator and verify
    operatorTree.delete(1);
    console.log(operatorTree.has(1)); // false;
    console.log(operatorTree.size); // 4;

    // Get tree height for optimization analysis
    const treeHeight = operatorTree.getHeight();
    console.log(treeHeight); // > 0;

    // Remaining operators are still accessible
    const remaining = operatorTree.get(2);
    console.log(remaining); // defined;

// Find lowest common ancestor
 const bst = new BST<number>([20, 10, 30, 5, 15, 25, 35, 3, 7, 12, 18]);

    // LCA helper function
    const findLCA = (num1: number, num2: number): number | undefined => {
      const path1 = bst.getPathToRoot(num1);
      const path2 = bst.getPathToRoot(num2);
      // Find the first common ancestor
      return findFirstCommon(path1, path2);
    };

    function findFirstCommon(arr1: (number | undefined)[], arr2: (number | undefined)[]): number | undefined {
      for (const num of arr1) {
        if (arr2.indexOf(num) !== -1) {
          return num;
        }
      }
      return undefined;
    }

    // Assertions
    console.log(findLCA(3, 10)); // 7;
    console.log(findLCA(5, 35)); // 15;
    console.log(findLCA(20, 30)); // 25;

Extends

BinaryTree<K, V, R>

Extended by

Type Parameters

K

K = any

The type of the key.

V

V = any

The type of the value.

R

R = any

The type of the raw data object (if using toEntryFn).

Node Order: Each node's left child has a lesser value, and the right child has a greater value.
Unique Keys: No duplicate keys in a standard BST.
Efficient Search: Enables quick search, minimum, and maximum operations.
Inorder Traversal: Yields nodes in ascending order.
Logarithmic Operations: Ideal operations like insertion, deletion, and searching are O(log n) time-efficient.
Balance Variability: Can become unbalanced; special types maintain balance.
No Auto-Balancing: Standard BSTs don't automatically balance themselves.

Implements

IBinaryTree<K, V, R>

Constructors

Constructor

new BST<K, V, R>(keysNodesEntriesOrRaws?, options?): BST<K, V, R>;

Defined in: data-structures/binary-tree/bst.ts:335

Creates an instance of BST.

Parameters

keysNodesEntriesOrRaws?

An iterable of items to set.

options?

BSTOptions<K, V, R>

Configuration options for the BST, including comparator.

Returns

BST<K, V, R>

Remarks

Time O(N log N) or O(N^2) depending on isBalanceAdd in addMany and input order. Space O(N).

Overrides

BinaryTree.constructor

Properties

comparator

Get Signature

get comparator(): Comparator<K>;

Defined in: data-structures/binary-tree/bst.ts:380

Gets the comparator function used by the tree.

Remarks

Time O(1)

Returns

Comparator<K>

The comparator function.

isDuplicate

Get Signature

get isDuplicate(): boolean;

Defined in: data-structures/binary-tree/binary-tree.ts:322

Gets whether the tree allows duplicate keys.

Remarks

Time O(1)

Returns

boolean

True if duplicates are allowed, false otherwise.

Implementation of

IBinaryTree.isDuplicate

Inherited from

BinaryTree.isDuplicate

isMapMode

Get Signature

get isMapMode(): boolean;

Defined in: data-structures/binary-tree/binary-tree.ts:310

Gets whether the tree is in Map mode.

Remarks

In Map mode (default), values are stored in an external Map, and nodes only hold keys. If false, values are stored directly on the nodes. Time O(1)

Returns

boolean

True if in Map mode, false otherwise.

Implementation of

IBinaryTree.isMapMode

Inherited from

BinaryTree.isMapMode

NIL

Get Signature

get NIL(): BinaryTreeNode<K, V>;

Defined in: data-structures/binary-tree/binary-tree.ts:373

Gets the sentinel NIL node (used in self-balancing trees like Red-Black Tree).

Remarks

Time O(1)

Returns

BinaryTreeNode<K, V>

The NIL node.

Implementation of

IBinaryTree.NIL

Inherited from

BinaryTree.NIL

root

Get Signature

get root(): OptNode<BSTNode<K, V>>;

Defined in: data-structures/binary-tree/bst.ts:363

Gets the root node of the tree.

Remarks

Time O(1)

Returns

OptNode<BSTNode<K, V>>

The root node.

Implementation of

IBinaryTree.root

Overrides

BinaryTree.root

size

Get Signature

get size(): number;

Defined in: data-structures/binary-tree/binary-tree.ts:361

Gets the number of nodes in the tree.

Remarks

Time O(1)

Returns

number

The size of the tree.

Implementation of

IBinaryTree.size

Inherited from

BinaryTree.size

store

Get Signature

get store(): Map<K, BinaryTreeNode<K, V>>;

Defined in: data-structures/binary-tree/binary-tree.ts:337

Gets the external value store (used in Map mode).

Remarks

Time O(1)

Returns

Map<K, BinaryTreeNode<K, V>>

The map storing key-value pairs.

Implementation of

IBinaryTree.store

Inherited from

BinaryTree.store

toEntryFn

Get Signature

get toEntryFn(): ToEntryFn<K, V, R> | undefined;

Defined in: data-structures/binary-tree/binary-tree.ts:385

Gets the function used to convert raw data objects (R) into [key, value] entries.

Remarks

Time O(1)

Returns

ToEntryFn<K, V, R> | undefined

The conversion function.

Implementation of

IBinaryTree.toEntryFn

Inherited from

BinaryTree.toEntryFn

Methods

[iterator]()

iterator: IterableIterator<[K, V | undefined]>;

Defined in: data-structures/base/iterable-entry-base.ts:22

Default iterator yielding [key, value] entries.

Parameters

args

...unknown[]

Returns

IterableIterator<[K, V | undefined]>

Iterator of [K, V].

Remarks

Time O(n) to iterate, Space O(1)

Implementation of

IBinaryTree.[iterator]

Inherited from

BinaryTree.[iterator]

add()

add(keyNodeOrEntry): boolean;

Defined in: data-structures/binary-tree/binary-tree.ts:607

Adds a new node to the tree.

Parameters

keyNodeOrEntry

The key, node, or entry to add.

Returns

boolean

True if the addition was successful, false otherwise.

Remarks

Time O(log N), For BST, Red-Black Tree, and AVL Tree subclasses, the worst-case time is O(log N). This implementation adds the node at the first available position in a level-order (BFS) traversal. This is NOT a Binary Search Tree insertion. Time O(N), where N is the number of nodes. It must traverse level-by-level to find an empty slot. Space O(N) in the worst case for the BFS queue (e.g., a full last level).

Example

// Add a single node
 const tree = new BinaryTree<number>();
    tree.add(1);
    tree.add(2);
    tree.add(3);
    console.log(tree.size); // 3;
    console.log(tree.has(1)); // true;

Implementation of

IBinaryTree.add

Inherited from

BinaryTree.add

addMany()

addMany(keysNodesEntriesOrRaws): boolean[];

Defined in: data-structures/binary-tree/binary-tree.ts:778

Adds multiple items to the tree.

Parameters

keysNodesEntriesOrRaws

An iterable of items to set.

Returns

boolean[]

An array of booleans indicating the success of each individual set operation.

Remarks

Time O(N * M), where N is the number of items to set and M is the size of the tree at insertion (due to O(M) set operation). Space O(M) (from set) + O(N) (for the inserted array).

Example

// Bulk add
 const tree = new BinaryTree<number>();
    tree.addMany([1, 2, 3, 4, 5]);
    console.log(tree.size); // 5;

Implementation of

IBinaryTree.addMany

Inherited from

BinaryTree.addMany

bfs()

Performs a Breadth-First Search (BFS) or Level-Order traversal.

Remarks

Time O(N), visits every node. Space O(N) in the worst case for the queue.

Template

The type of the callback function.

Param

Function to call on each node.

Param

The node to start from.

Param

The traversal method.

Call Signature

bfs(): (K | undefined)[];

Defined in: data-structures/binary-tree/bst.ts:611

BinaryTree level-order traversal

Returns

(K | undefined)[]

Example

// Breadth-first traversal
 const bst = new BST<number>([5, 3, 7]);
    const result = bst.bfs(node => node.key);
    console.log(result.length); // 3;

Implementation of

IBinaryTree.bfs

Overrides

BinaryTree.bfs

Call Signature

bfs<C>(
   callback, 
   startNode?, 
   iterationType?): ReturnType<C>[];

Defined in: data-structures/binary-tree/bst.ts:612

BinaryTree level-order traversal

Type Parameters

C

C extends NodeCallback<BSTNode<K, V>>

Parameters

callback

C

startNode?

iterationType?

IterationType

Returns

ReturnType<C>[]

Example

// Breadth-first traversal
 const bst = new BST<number>([5, 3, 7]);
    const result = bst.bfs(node => node.key);
    console.log(result.length); // 3;

Implementation of

IBinaryTree.bfs

Overrides

BinaryTree.bfs

ceiling()

Call Signature

ceiling(keyNodeEntryOrPredicate): K | undefined;

Defined in: data-structures/binary-tree/bst.ts:1531

Returns the first key with a value >= target. Equivalent to Java TreeMap.ceiling. Time Complexity: O(log n) average, O(h) worst case. Space Complexity: O(h) for recursion, O(1) for iteration.

Parameters

keyNodeEntryOrPredicate

Returns

K | undefined

Example

// Find the least key ≥ target
 const bst = new BST<number>([10, 20, 30, 40, 50]);
    console.log(bst.ceiling(25)); // 30;
    console.log(bst.ceiling(30)); // 30;
    console.log(bst.ceiling(55)); // undefined;

Call Signature

ceiling<C>(
   keyNodeEntryOrPredicate, 
   callback, 
iterationType?): ReturnType<C>;

Defined in: data-structures/binary-tree/bst.ts:1546

Returns the first node with a key >= target and applies callback. Time Complexity: O(log n) average, O(h) worst case. Space Complexity: O(h) for recursion, O(1) for iteration.

Type Parameters

C

C extends NodeCallback<BSTNode<K, V>>

Parameters

keyNodeEntryOrPredicate

callback

C

iterationType?

IterationType

Returns

ReturnType<C>

clear()

clear(): void;

Defined in: data-structures/binary-tree/binary-tree.ts:1497

Clears the tree of all nodes and values.

Returns

void

Remarks

Time O(N) if in Map mode (due to _store.clear()), O(1) otherwise. Space O(1)

Example

// Remove all nodes
 const tree = new BinaryTree<number>([1, 2, 3]);
    tree.clear();
    console.log(tree.isEmpty()); // true;

Implementation of

IBinaryTree.clear

Inherited from

BinaryTree.clear

clone()

clone(): this;

Defined in: data-structures/binary-tree/binary-tree.ts:2675

Clones the tree.

Returns

this

A new, cloned instance of the tree.

Remarks

Time O(N * M), where N is the number of nodes and M is the tree size during insertion (due to bfs + set, and set is O(M)). Space O(N) for the new tree and the BFS queue.

Example

// Deep copy
 const tree = new BinaryTree<number>([1, 2, 3]);
    const copy = tree.clone();
    copy.delete(1);
    console.log(tree.has(1)); // true;

Implementation of

IBinaryTree.clone

Inherited from

BinaryTree.clone

createNode()

createNode(key, value?): BSTNode<K, V>;

Defined in: data-structures/binary-tree/bst.ts:392

(Protected) Creates a new BST node.

Parameters

key

K

The key for the new node.

value?

V

The value for the new node (used if not in Map mode).

Returns

BSTNode<K, V>

The newly created BSTNode.

Remarks

Time O(1), Space O(1)

Implementation of

IBinaryTree.createNode

Overrides

BinaryTree.createNode

createTree()

createTree(options?): this;

Defined in: data-structures/binary-tree/binary-tree.ts:408

Creates a new, empty tree of the same type and configuration.

Parameters

options?

Partial<BinaryTreeOptions<K, V, R>>

Optional overrides for the new tree's options.

Returns

this

A new, empty tree instance.

Remarks

Time O(1) (excluding options cloning), Space O(1)

Implementation of

IBinaryTree.createTree

Inherited from

BinaryTree.createTree

delete()

delete(keyNodeEntryRawOrPredicate): BinaryTreeDeleteResult<BinaryTreeNode<K, V>>[];

Defined in: data-structures/binary-tree/binary-tree.ts:965

Deletes a node from the tree.

Parameters

keyNodeEntryRawOrPredicate

| NodePredicate<BinaryTreeNode<K, V> | null> | BTNRep<K, V, BinaryTreeNode<K, V>>

The node to delete.

Returns

BinaryTreeDeleteResult<BinaryTreeNode<K, V>>[]

An array containing deletion results (for compatibility with self-balancing trees).

Remarks

Time O(log N), For BST, Red-Black Tree, and AVL Tree subclasses, the worst-case time is O(log N). This implementation finds the node, and if it has two children, swaps it with the rightmost node of its left subtree (in-order predecessor) before deleting. Time O(N) in the worst case. O(N) to find the node (getNode) and O(H) (which is O(N) worst-case) to find the rightmost node. Space O(1) (if getNode is iterative, which it is).

Example

// Remove a node
 const tree = new BinaryTree<number>([1, 2, 3, 4, 5]);
    tree.delete(3);
    console.log(tree.has(3)); // false;
    console.log(tree.size); // 4;

Implementation of

IBinaryTree.delete

Inherited from

BinaryTree.delete

deleteWhere()

deleteWhere(
   keyNodeEntryOrPredicate, 
   onlyOne?, 
   startNode?, 
   iterationType?): BinaryTreeDeleteResult<BSTNode<K, V>>[];

Defined in: data-structures/binary-tree/bst.ts:2339

Deletes nodes that match a key, node, entry, predicate, or range.

Parameters

keyNodeEntryOrPredicate

The search criteria. Can be one of:

A key (type K): searches for exact key match using the comparator.
A BSTNode: searches for the matching node in the tree.
An entry tuple: searches for the key-value pair.
A NodePredicate function: tests each node and returns true for matches.
A Range object: searches for nodes whose keys fall within the specified range (inclusive/exclusive based on range settings).
null or undefined: treated as no match, returns empty results.

onlyOne?

boolean = false

If true, stops the search after finding the first match and only deletes that one node. If false (default), searches for and deletes all matching nodes.

startNode?

The node to start the search from. Can be:

A key, node, or entry: the method resolves it to a node and searches from that subtree.
null or undefined: defaults to the root, searching the entire tree.
Default value: this._root (the tree's root).

iterationType?

IterationType = ...

Controls the internal traversal implementation:

'RECURSIVE': uses recursive function calls for traversal.
'ITERATIVE': uses explicit stack-based iteration.
Default: this.iterationType (the tree's default iteration mode).

Returns

BinaryTreeDeleteResult<BSTNode<K, V>>[]

A Map<K, boolean> containing the deletion results:

Key: the matched node's key.
Value: true if the deletion succeeded, false if it failed (e.g., key not found during deletion phase).
If no nodes match the search criteria, the returned map is empty.

Remarks

Time Complexity: O(N) for search + O(M log N) for M deletions, where N is tree size. Space Complexity: O(M) for storing matched nodes and result map.

dfs()

Performs a Depth-First Search (DFS) traversal.

Remarks

Time O(N), visits every node. Space O(log N) for the call/explicit stack. O(N) worst-case.

Template

The type of the callback function.

Param

Function to call on each node.

Param

The traversal order ('IN', 'PRE', 'POST').

Param

If true, stops after the first callback.

Param

The node to start from.

Param

The traversal method.

Call Signature

dfs(): (K | undefined)[];

Defined in: data-structures/binary-tree/bst.ts:511

Depth-first search traversal

Returns

(K | undefined)[]

Example

// Depth-first traversal
 const bst = new BST<number>([5, 3, 7, 1, 4]);
    const inOrder = bst.dfs(node => node.key, 'IN');
    console.log(inOrder); // [1, 3, 4, 5, 7];

Implementation of

IBinaryTree.dfs

Overrides

BinaryTree.dfs

Call Signature

dfs<C>(
   callback, 
   pattern?, 
   onlyOne?, 
   startNode?, 
   iterationType?): ReturnType<C>[];

Defined in: data-structures/binary-tree/bst.ts:513

Depth-first search traversal

Type Parameters

C

C extends NodeCallback<BSTNode<K, V>>

Parameters

callback

C

pattern?

DFSOrderPattern

onlyOne?

boolean

startNode?

iterationType?

IterationType

Returns

ReturnType<C>[]

Example

// Depth-first traversal
 const bst = new BST<number>([5, 3, 7, 1, 4]);
    const inOrder = bst.dfs(node => node.key, 'IN');
    console.log(inOrder); // [1, 3, 4, 5, 7];

Implementation of

IBinaryTree.dfs

Overrides

BinaryTree.dfs

ensureNode()

ensureNode(keyNodeOrEntry, iterationType?): OptNode<BSTNode<K, V>>;

Defined in: data-structures/binary-tree/bst.ts:404

Ensures the input is a node. If it's a key or entry, it searches for the node.

Parameters

keyNodeOrEntry

The item to resolve to a node.

iterationType?

IterationType = ...

The traversal method to use if searching.

Returns

OptNode<BSTNode<K, V>>

The resolved node, or undefined if not found.

Remarks

Time O(log N) (height of the tree), O(N) worst-case.

Overrides

BinaryTree.ensureNode

entries()

entries(): IterableIterator<[K, V | undefined]>;

Defined in: data-structures/base/iterable-entry-base.ts:31

Iterate over [key, value] pairs (may yield undefined values).

Returns

IterableIterator<[K, V | undefined]>

Iterator of [K, V | undefined].

Remarks

Time O(n), Space O(1)

Implementation of

IBinaryTree.entries

Inherited from

BinaryTree.entries

every()

every(predicate, thisArg?): boolean;

Defined in: data-structures/base/iterable-entry-base.ts:66

Test whether all entries satisfy the predicate.

Parameters

predicate

EntryCallback<K, V | undefined, boolean>

(key, value, index, self) => boolean.

thisArg?

unknown

Optional this for callback.

Returns

boolean

true if all pass; otherwise false.

Remarks

Time O(n), Space O(1)

Implementation of

IBinaryTree.every

Inherited from

BinaryTree.every

filter()

filter(predicate, thisArg?): this;

Defined in: data-structures/binary-tree/binary-tree.ts:2726

Creates a new tree containing only the entries that satisfy the predicate.

Parameters

predicate

EntryCallback<K, V | undefined, boolean>

A function to test each [key, value] pair.

thisArg?

unknown

this context for the predicate.

Returns

this

A new, filtered tree.

Remarks

Time O(N * M), where N is nodes in this tree, and M is size of the new tree during insertion (O(N) iteration + O(M) set for each item). Space O(N) for the new tree.

Example

// Filter nodes by condition
 const tree = new BinaryTree<number>([1, 2, 3, 4]);
    const result = tree.filter((_, key) => key > 2);
    console.log(result.size); // 2;

Implementation of

IBinaryTree.filter

Inherited from

BinaryTree.filter

find()

find(callbackfn, thisArg?): [K, V | undefined] | undefined;

Defined in: data-structures/base/iterable-entry-base.ts:114

Find the first entry that matches a predicate.

Parameters

callbackfn

EntryCallback<K, V | undefined, boolean>

(key, value, index, self) => boolean.

thisArg?

unknown

Optional this for callback.

Returns

[K, V | undefined] | undefined

Matching [key, value] or undefined.

Remarks

Time O(n), Space O(1)

Implementation of

IBinaryTree.find

Inherited from

BinaryTree.find

floor()

Call Signature

floor(keyNodeEntryOrPredicate): K | undefined;

Defined in: data-structures/binary-tree/bst.ts:1740

Returns the first key with a value <= target. Equivalent to Java TreeMap.floor. Time Complexity: O(log n) average, O(h) worst case. Space Complexity: O(h) for recursion, O(1) for iteration.

Parameters

keyNodeEntryOrPredicate

Returns

K | undefined

Example

// Find the greatest key ≤ target
 const bst = new BST<number>([10, 20, 30, 40, 50]);
    console.log(bst.floor(25)); // 20;
    console.log(bst.floor(10)); // 10;
    console.log(bst.floor(5)); // undefined;

Call Signature

floor<C>(
   keyNodeEntryOrPredicate, 
   callback, 
iterationType?): ReturnType<C>;

Defined in: data-structures/binary-tree/bst.ts:1755

Returns the first node with a key <= target and applies callback. Time Complexity: O(log n) average, O(h) worst case. Space Complexity: O(h) for recursion, O(1) for iteration.

Type Parameters

C

C extends NodeCallback<BSTNode<K, V>>

Parameters

keyNodeEntryOrPredicate

callback

C

iterationType?

IterationType

Returns

ReturnType<C>

forEach()

forEach(callbackfn, thisArg?): void;

Defined in: data-structures/base/iterable-entry-base.ts:99

Visit each entry, left-to-right.

Parameters

callbackfn

EntryCallback<K, V | undefined, void>

(key, value, index, self) => void.

thisArg?

unknown

Optional this for callback.

Returns

void

Remarks

Time O(n), Space O(1)

Implementation of

IBinaryTree.forEach

Inherited from

BinaryTree.forEach

get()

get(
   keyNodeEntryOrPredicate, 
   startNode?, 
   iterationType?): V | undefined;

Defined in: data-structures/binary-tree/binary-tree.ts:1339

Gets the value associated with a key.

Parameters

keyNodeEntryOrPredicate

The key, node, or entry to get the value for.

startNode?

The node to start searching from (if not in Map mode).

iterationType?

IterationType = ...

The traversal method (if not in Map mode).

Returns

V | undefined

The associated value, or undefined.

Remarks

Time O(log N), For BST, Red-Black Tree, and AVL Tree subclasses, the worst-case time is O(log N). Time O(1) if in Map mode. O(N) if not in Map mode (uses getNode). Space O(1) if in Map mode. O(H) or O(N) otherwise.

Example

// Retrieve value by key
 const tree = new BinaryTree<number, string>([[1, 'root'], [2, 'left'], [3, 'right']]);
    console.log(tree.get(2)); // 'left';
    console.log(tree.get(99)); // undefined;

Implementation of

IBinaryTree.get

Inherited from

BinaryTree.get

getDepth()

getDepth(dist, startNode?): number;

Defined in: data-structures/binary-tree/binary-tree.ts:1695

Gets the depth of a node (distance from startNode).

Parameters

dist

The node to find the depth of.

startNode?

The node to measure depth from (defaults to root).

Returns

number

The depth (0 if dist is startNode).

Remarks

Time O(H), where H is the depth of the dist node relative to startNode. O(N) worst-case. Space O(1).

Example

// Get depth of a node
 const tree = new BinaryTree<number>([1, 2, 3, 4, 5]);
    const node = tree.getNode(4);
    console.log(tree.getDepth(node!)); // 2;

Implementation of

IBinaryTree.getDepth

Inherited from

BinaryTree.getDepth

getHeight()

getHeight(startNode?, iterationType?): number;

Defined in: data-structures/binary-tree/binary-tree.ts:1758

Gets the maximum height of the tree (longest path from startNode to a leaf).

Parameters

startNode?

The node to start measuring from.

iterationType?

IterationType = ...

The traversal method.

Returns

number

The height ( -1 for an empty tree, 0 for a single-node tree).

Remarks

Time O(N), as it must visit every node. Space O(H) for recursive stack (O(N) worst-case) or O(N) for iterative stack (storing node + depth).

Example

// Get tree height
 const tree = new BinaryTree<number>([1, 2, 3, 4, 5]);
    console.log(tree.getHeight()); // 2;

Implementation of

IBinaryTree.getHeight

Inherited from

BinaryTree.getHeight

getLeftMost()

Finds the leftmost node in a subtree (the node with the smallest key in a BST).

Remarks

Time O(H), where H is the height of the left spine. O(N) worst-case. Space O(H) for recursive/trampoline stack.

Template

The type of the callback function.

Param

A function to call on the leftmost node.

Param

The subtree root to search from.

Param

The traversal method.

Call Signature

getLeftMost(): K | undefined;

Defined in: data-structures/binary-tree/binary-tree.ts:1885

Returns

K | undefined

Implementation of

IBinaryTree.getLeftMost

Inherited from

BinaryTree.getLeftMost

Call Signature

getLeftMost<C>(
   callback, 
   startNode?, 
iterationType?): ReturnType<C>;

Defined in: data-structures/binary-tree/binary-tree.ts:1887

Type Parameters

C

C extends NodeCallback<BinaryTreeNode<K, V> | undefined>

Parameters

callback

C

startNode?

iterationType?

IterationType

Returns

ReturnType<C>

Implementation of

IBinaryTree.getLeftMost

Inherited from

BinaryTree.getLeftMost

getMinHeight()

getMinHeight(startNode?, iterationType?): number;

Defined in: data-structures/binary-tree/binary-tree.ts:1800

Gets the minimum height of the tree (shortest path from startNode to a leaf).

Parameters

startNode?

The node to start measuring from.

iterationType?

IterationType = ...

The traversal method.

Returns

number

The minimum height (-1 for empty, 0 for single node).

Remarks

Time O(N), as it must visit every node. Space O(H) for recursive stack (O(N) worst-case) or O(N) for iterative (due to depths Map).

Implementation of

IBinaryTree.getMinHeight

Inherited from

BinaryTree.getMinHeight

getNode()

getNode(
   keyNodeEntryOrPredicate, 
   startNode?, 
iterationType?): OptNode<BSTNode<K, V>>;

Defined in: data-structures/binary-tree/bst.ts:816

Gets the first node matching a predicate.

Parameters

keyNodeEntryOrPredicate

The key, node, entry, or predicate function to search for.

startNode?

BSTNOptKeyOrNode<K, BSTNode<K, V>> = ...

The node to start the search from.

iterationType?

IterationType = ...

The traversal method.

Returns

OptNode<BSTNode<K, V>>

The first matching node, or undefined if not found.

Remarks

Time O(log N) if searching by key, O(N) if searching by predicate. Space O(log N) or O(N).

Example

// Get node object by key
 const bst = new BST<number, string>([[5, 'root'], [3, 'left'], [7, 'right']]);
    const node = bst.getNode(3);
    console.log(node?.key); // 3;
    console.log(node?.value); // 'left';

Implementation of

IBinaryTree.getNode

Overrides

BinaryTree.getNode

getNodes()

getNodes(
   keyNodeEntryOrPredicate, 
   onlyOne?, 
   startNode?, 
   iterationType?): BinaryTreeNode<K, V>[];

Defined in: data-structures/binary-tree/binary-tree.ts:1197

Gets all nodes matching a predicate.

Parameters

keyNodeEntryOrPredicate

The key, node, entry, or predicate function to search for.

onlyOne?

boolean

If true, stops after finding the first match.

startNode?

The node to start the search from.

iterationType?

IterationType

The traversal method.

Returns

BinaryTreeNode<K, V>[]

An array of matching nodes.

Remarks

Time O(N) (via search). Space O(H) or O(N) (via search).

Example

// Get nodes by condition
 const tree = new BinaryTree<number>([1, 2, 3, 4, 5]);
    const nodes = tree.getNodes(node => node.key > 3);
    console.log(nodes.length); // 2;

Inherited from

BinaryTree.getNodes

getPathToRoot()

Gets the path from a given node up to the root.

Remarks

Time O(H), where H is the depth of the beginNode. O(N) worst-case. Space O(H) for the result array.

Template

The type of the callback function.

Param

The node to start the path from.

Param

A function to call on each node in the path.

Param

If true, returns the path from root-to-node.

Call Signature

getPathToRoot(beginNode): (K | undefined)[];

Defined in: data-structures/binary-tree/binary-tree.ts:1847

Parameters

beginNode

Returns

(K | undefined)[]

Implementation of

IBinaryTree.getPathToRoot

Inherited from

BinaryTree.getPathToRoot

Call Signature

getPathToRoot<C>(
   beginNode, 
   callback, 
   isReverse?): ReturnType<C>[];

Defined in: data-structures/binary-tree/binary-tree.ts:1851

Type Parameters

C

C extends NodeCallback<BinaryTreeNode<K, V> | undefined>

Parameters

beginNode

callback

C

isReverse?

boolean

Returns

ReturnType<C>[]

Implementation of

IBinaryTree.getPathToRoot

Inherited from

BinaryTree.getPathToRoot

getPredecessor()

getPredecessor(node): BinaryTreeNode<K, V>;

Defined in: data-structures/binary-tree/binary-tree.ts:1985

Gets the Morris traversal predecessor (rightmost node in the left subtree, or node itself).

Parameters

node

BinaryTreeNode<K, V>

The node to find the predecessor for.

Returns

BinaryTreeNode<K, V>

The Morris predecessor.

Remarks

This is primarily a helper for Morris traversal. Time O(H), where H is the height of the left subtree. O(N) worst-case. Space O(1).

Inherited from

BinaryTree.getPredecessor

getRightMost()

Finds the rightmost node in a subtree (the node with the largest key in a BST).

Remarks

Time O(H), where H is the height of the right spine. O(N) worst-case. Space O(H) for recursive/trampoline stack.

Template

The type of the callback function.

Param

A function to call on the rightmost node.

Param

The subtree root to search from.

Param

The traversal method.

Call Signature

getRightMost(): K | undefined;

Defined in: data-structures/binary-tree/binary-tree.ts:1932

Returns

K | undefined

Implementation of

IBinaryTree.getRightMost

Inherited from

BinaryTree.getRightMost

Call Signature

getRightMost<C>(
   callback, 
   startNode?, 
iterationType?): ReturnType<C>;

Defined in: data-structures/binary-tree/binary-tree.ts:1934

Type Parameters

C

C extends NodeCallback<BinaryTreeNode<K, V> | undefined>

Parameters

callback

C

startNode?

iterationType?

IterationType

Returns

ReturnType<C>

Implementation of

IBinaryTree.getRightMost

Inherited from

BinaryTree.getRightMost

getSuccessor()

getSuccessor(x?): BinaryTreeNode<K, V> | null | undefined;

Defined in: data-structures/binary-tree/binary-tree.ts:2006

Gets the in-order successor of a node in a BST.

Parameters

x?

K | BinaryTreeNode<K, V> | null

The node to find the successor of.

Returns

BinaryTreeNode<K, V> | null | undefined

The successor node, or null/undefined if none exists.

Remarks

Time O(H), where H is the tree height. O(N) worst-case. Space O(H) (due to getLeftMost stack).

Inherited from

BinaryTree.getSuccessor

has()

has(
   keyNodeEntryOrPredicate?, 
   startNode?, 
   iterationType?): boolean;

Defined in: data-structures/binary-tree/binary-tree.ts:1423

Checks if a node matching the predicate exists in the tree.

Parameters

keyNodeEntryOrPredicate?

The key, node, entry, or predicate to check for.

startNode?

The node to start the search from.

iterationType?

IterationType

The traversal method.

Returns

boolean

True if a matching node exists, false otherwise.

Remarks

Time O(log N), For BST, Red-Black Tree, and AVL Tree subclasses, the worst-case time is O(log N). Time O(N) in the worst case (via search). Space O(H) or O(N) (via search).

Example

// BinaryTree get and has operations
 const tree = new BinaryTree(
      [
        [5, 'five'],
        [3, 'three'],
        [7, 'seven'],
        [1, 'one'],
        [4, 'four'],
        [6, 'six'],
        [8, 'eight']
      ],
      { isMapMode: false }
    );

    // Check if key exists
    console.log(tree.has(5)); // true;
    console.log(tree.has(10)); // false;

    // Get value by key
    console.log(tree.get(3)); // 'three';
    console.log(tree.get(7)); // 'seven';
    console.log(tree.get(100)); // undefined;

    // Get node structure
    const node = tree.getNode(5);
    console.log(node?.key); // 5;
    console.log(node?.value); // 'five';

Implementation of

IBinaryTree.has

Inherited from

BinaryTree.has

hasValue()

hasValue(value): boolean;

Defined in: data-structures/base/iterable-entry-base.ts:143

Whether there exists an entry with the given value.

Parameters

value

V | undefined

Value to test.

Returns

boolean

true if found; otherwise false.

Remarks

Time O(n), Space O(1)

Implementation of

IBinaryTree.hasValue

Inherited from

BinaryTree.hasValue

higher()

Call Signature

higher(keyNodeEntryOrPredicate): K | undefined;

Defined in: data-structures/binary-tree/bst.ts:1635

Returns the first key with a value > target. Equivalent to Java TreeMap.higher. Time Complexity: O(log n) average, O(h) worst case. Space Complexity: O(h) for recursion, O(1) for iteration.

Parameters

keyNodeEntryOrPredicate

Returns

K | undefined

Example

// Find the least key strictly > target
 const bst = new BST<number>([10, 20, 30, 40]);
    console.log(bst.higher(20)); // 30;
    console.log(bst.higher(40)); // undefined;

Call Signature

higher<C>(
   keyNodeEntryOrPredicate, 
   callback, 
iterationType?): ReturnType<C>;

Defined in: data-structures/binary-tree/bst.ts:1650

Returns the first node with a key > target and applies callback. Time Complexity: O(log n) average, O(h) worst case. Space Complexity: O(h) for recursion, O(1) for iteration.

Type Parameters

C

C extends NodeCallback<BSTNode<K, V>>

Parameters

keyNodeEntryOrPredicate

callback

C

iterationType?

IterationType

Returns

ReturnType<C>

isAVLBalanced()

isAVLBalanced(iterationType?): boolean;

Defined in: data-structures/binary-tree/bst.ts:2162

Checks if the tree meets the AVL balance condition (height difference <= 1).

Parameters

iterationType?

IterationType = ...

The traversal method.

Returns

boolean

True if the tree is AVL balanced, false otherwise.

Remarks

Time O(N), as it must visit every node to compute height. Space O(log N) for recursion or O(N) for iterative map.

Example

// Check if tree is height-balanced
 const bst = new BST<number>([3, 1, 5, 2, 4]);
    console.log(bst.isAVLBalanced()); // true;

isBST()

isBST(startNode?, iterationType?): boolean;

Defined in: data-structures/binary-tree/binary-tree.ts:1605

Checks if the tree is a valid Binary Search Tree (BST).

Parameters

startNode?

The node to start checking from.

iterationType?

IterationType = ...

The traversal method.

Returns

boolean

True if it's a valid BST, false otherwise.

Remarks

Time O(N), as it must visit every node. Space O(H) for the call stack (recursive) or explicit stack (iterative), where H is the tree height (O(N) worst-case).

Example

// Check BST property
 const tree = new BinaryTree<number>([1, 2, 3]);
    // BinaryTree doesn't guarantee BST order
    console.log(typeof tree.isBST()); // 'boolean';

Implementation of

IBinaryTree.isBST

Inherited from

BinaryTree.isBST

isEmpty()

isEmpty(): boolean;

Defined in: data-structures/binary-tree/binary-tree.ts:1543

Checks if the tree is empty.

Returns

boolean

True if the tree has no nodes, false otherwise.

Remarks

Time O(1), Space O(1)

Example

// Check empty
 console.log(new BinaryTree().isEmpty()); // true;

Implementation of

IBinaryTree.isEmpty

Inherited from

BinaryTree.isEmpty

isEntry()

isEntry(keyNodeOrEntry): keyNodeOrEntry is BTNEntry<K, V>;

Defined in: data-structures/binary-tree/binary-tree.ts:545

Checks if the given item is a [key, value] entry pair.

Parameters

keyNodeOrEntry

The item to check.

Returns

keyNodeOrEntry is BTNEntry<K, V>

True if it's an entry, false otherwise.

Remarks

Time O(1), Space O(1)

Inherited from

BinaryTree.isEntry

isLeaf()

isLeaf(keyNodeOrEntry): boolean;

Defined in: data-structures/binary-tree/binary-tree.ts:531

Checks if a node is a leaf (has no real children).

Parameters

keyNodeOrEntry

The node to check.

Returns

boolean

True if the node is a leaf, false otherwise.

Remarks

Time O(N) if a key/entry is passed (due to ensureNode). O(1) if a node is passed. Space O(1) or O(H) (from ensureNode).

Inherited from

BinaryTree.isLeaf

isNIL()

isNIL(keyNodeOrEntry): boolean;

Defined in: data-structures/binary-tree/binary-tree.ts:500

Checks if the given item is the sentinel NIL node.

Parameters

keyNodeOrEntry

The item to check.

Returns

boolean

True if it's the NIL node, false otherwise.

Remarks

Time O(1), Space O(1)

Inherited from

BinaryTree.isNIL

isNode()

isNode(keyNodeOrEntry): keyNodeOrEntry is BSTNode<K, V>;

Defined in: data-structures/binary-tree/bst.ts:418

Checks if the given item is a BSTNode instance.

Parameters

keyNodeOrEntry

The item to check.

Returns

keyNodeOrEntry is BSTNode<K, V>

True if it's a BSTNode, false otherwise.

Remarks

Time O(1), Space O(1)

Overrides

BinaryTree.isNode

isPerfectlyBalanced()

isPerfectlyBalanced(startNode?): boolean;

Defined in: data-structures/binary-tree/binary-tree.ts:1554

Checks if the tree is perfectly balanced.

Parameters

startNode?

The node to start checking from.

Returns

boolean

True if perfectly balanced, false otherwise.

Remarks

A tree is perfectly balanced if the difference between min and max height is at most 1. Time O(N), as it requires two full traversals (getMinHeight and getHeight). Space O(H) or O(N) (from height calculation).

Implementation of

IBinaryTree.isPerfectlyBalanced

Inherited from

BinaryTree.isPerfectlyBalanced

isRange()

isRange(keyNodeEntryOrPredicate): keyNodeEntryOrPredicate is Range<K>;

Defined in: data-structures/binary-tree/binary-tree.ts:511

Checks if the given item is a Range object.

Parameters

keyNodeEntryOrPredicate

The item to check.

Returns

keyNodeEntryOrPredicate is Range<K>

True if it's a Range, false otherwise.

Remarks

Time O(1), Space O(1)

Inherited from

BinaryTree.isRange

isRaw()

isRaw(keyNodeEntryOrRaw): keyNodeEntryOrRaw is R;

Defined in: data-structures/binary-tree/binary-tree.ts:460

Checks if the given item is a raw data object (R) that needs conversion via toEntryFn.

Parameters

keyNodeEntryOrRaw

The item to check.

Returns

keyNodeEntryOrRaw is R

True if it's a raw object, false otherwise.

Remarks

Time O(1), Space O(1)

Inherited from

BinaryTree.isRaw

isRealNode()

isRealNode(keyNodeOrEntry): keyNodeOrEntry is BinaryTreeNode<K, V>;

Defined in: data-structures/binary-tree/binary-tree.ts:473

Checks if the given item is a "real" node (i.e., not null, undefined, or NIL).

Parameters

keyNodeOrEntry

The item to check.

Returns

keyNodeOrEntry is BinaryTreeNode<K, V>

True if it's a real node, false otherwise.

Remarks

Time O(1), Space O(1)

Inherited from

BinaryTree.isRealNode

isRealNodeOrNull()

isRealNodeOrNull(keyNodeOrEntry): keyNodeOrEntry is BinaryTreeNode<K, V> | null;

Defined in: data-structures/binary-tree/binary-tree.ts:487

Checks if the given item is either a "real" node or null.

Parameters

keyNodeOrEntry

The item to check.

Returns

keyNodeOrEntry is BinaryTreeNode<K, V> | null

True if it's a real node or null, false otherwise.

Remarks

Time O(1), Space O(1)

Inherited from

BinaryTree.isRealNodeOrNull

isValidKey()

isValidKey(key): key is K;

Defined in: data-structures/binary-tree/bst.ts:431

Checks if the given key is valid (comparable).

Parameters

key

unknown

The key to validate.

Returns

key is K

True if the key is valid, false otherwise.

Remarks

Time O(1)

Overrides

BinaryTree.isValidKey

keys()

keys(): IterableIterator<K>;

Defined in: data-structures/base/iterable-entry-base.ts:42

Iterate over keys only.

Returns

IterableIterator<K>

Iterator of keys.

Remarks

Time O(n), Space O(1)

Implementation of

IBinaryTree.keys

Inherited from

BinaryTree.keys

leaves()

Finds all leaf nodes in the tree.

Remarks

Time O(N), visits every node. Space O(H) for recursive or iterative stack.

Template

The type of the callback function.

Param

Function to call on each leaf node.

Param

The node to start from.

Param

The traversal method.

Call Signature

leaves(): (K | undefined)[];

Defined in: data-structures/binary-tree/binary-tree.ts:2297

Get leaf nodes

Returns

(K | undefined)[]

Example

// Get leaf nodes
 const tree = new BinaryTree<number>([1, 2, 3, 4, 5]);
    const leafKeys = tree.leaves(node => node.key);
    console.log(leafKeys.length); // > 0;

Implementation of

IBinaryTree.leaves

Inherited from

BinaryTree.leaves

Call Signature

leaves<C>(
   callback, 
   startNode?, 
   iterationType?): ReturnType<C>[];

Defined in: data-structures/binary-tree/binary-tree.ts:2299

Get leaf nodes

Type Parameters

C

C extends NodeCallback<BinaryTreeNode<K, V>>

Parameters

callback

C

startNode?

iterationType?

IterationType

Returns

ReturnType<C>[]

Example

// Get leaf nodes
 const tree = new BinaryTree<number>([1, 2, 3, 4, 5]);
    const leafKeys = tree.leaves(node => node.key);
    console.log(leafKeys.length); // > 0;

Implementation of

IBinaryTree.leaves

Inherited from

BinaryTree.leaves

lesserOrGreaterTraverse()

Traverses the tree and returns nodes that are lesser or greater than a target node.

Remarks

Time O(N), as it performs a full traversal. Space O(log N) or O(N).

Template

The type of the callback function.

Param

Function to call on matching nodes.

Param

1 for lesser, 1 for greater, 0 for equal.

Param

The node to compare against.

Param

The traversal method.

Call Signature

lesserOrGreaterTraverse(): (K | undefined)[];

Defined in: data-structures/binary-tree/bst.ts:1990

Returns

(K | undefined)[]

Call Signature

lesserOrGreaterTraverse<C>(
   callback, 
   lesserOrGreater?, 
   targetNode?, 
   iterationType?): ReturnType<C>[];

Defined in: data-structures/binary-tree/bst.ts:1992

Type Parameters

C

C extends NodeCallback<BSTNode<K, V>>

Parameters

callback

C

lesserOrGreater?

number

targetNode?

iterationType?

IterationType

Returns

ReturnType<C>[]

listLevels()

Returns a 2D array of nodes, grouped by level.

Remarks

Time O(N), visits every node. Space O(N) for the result array and the queue/stack.

Template

The type of the callback function.

Param

Function to call on each node.

Param

The node to start from.

Param

The traversal method.

Call Signature

listLevels(): (K | undefined)[][];

Defined in: data-structures/binary-tree/bst.ts:710

Level-order grouping

Returns

(K | undefined)[][]

Example

// Level-order grouping
 const bst = new BST<number>([5, 3, 7, 1, 4]);
    const levels = bst.listLevels(node => node.key);
    console.log(levels.length); // > 0;
    console.log(levels[0].length); // 1; // root level has 1 node
    const allKeys = levels.flat().sort((a, b) => a - b);
    console.log(allKeys); // [1, 3, 4, 5, 7];

Implementation of

IBinaryTree.listLevels

Overrides

BinaryTree.listLevels

Call Signature

listLevels<C>(
   callback, 
   startNode?, 
   iterationType?): ReturnType<C>[][];

Defined in: data-structures/binary-tree/bst.ts:712

Level-order grouping

Type Parameters

C

C extends NodeCallback<BSTNode<K, V>>

Parameters

callback

C

startNode?

iterationType?

IterationType

Returns

ReturnType<C>[][]

Example

// Level-order grouping
 const bst = new BST<number>([5, 3, 7, 1, 4]);
    const levels = bst.listLevels(node => node.key);
    console.log(levels.length); // > 0;
    console.log(levels[0].length); // 1; // root level has 1 node
    const allKeys = levels.flat().sort((a, b) => a - b);
    console.log(allKeys); // [1, 3, 4, 5, 7];

Implementation of

IBinaryTree.listLevels

Overrides

BinaryTree.listLevels

lower()

Call Signature

lower(keyNodeEntryOrPredicate): K | undefined;

Defined in: data-structures/binary-tree/bst.ts:1887

Returns the first key with a value < target. Equivalent to Java TreeMap.lower. Time Complexity: O(log n) average, O(h) worst case. Space Complexity: O(h) for recursion, O(1) for iteration.

Parameters

keyNodeEntryOrPredicate

Returns

K | undefined

Example

// Find the greatest key strictly < target
 const bst = new BST<number>([10, 20, 30, 40]);
    console.log(bst.lower(30)); // 20;
    console.log(bst.lower(10)); // undefined;

Call Signature

lower<C>(
   keyNodeEntryOrPredicate, 
   callback, 
iterationType?): ReturnType<C>;

Defined in: data-structures/binary-tree/bst.ts:1902

Returns the first node with a key < target and applies callback. Time Complexity: O(log n) average, O(h) worst case. Space Complexity: O(h) for recursion, O(1) for iteration.

Type Parameters

C

C extends NodeCallback<BSTNode<K, V>>

Parameters

keyNodeEntryOrPredicate

callback

C

iterationType?

IterationType

Returns

ReturnType<C>

map()

map<MK, MV, MR>(
   callback, 
   options?, 
thisArg?): BST<MK, MV, MR>;

Defined in: data-structures/binary-tree/bst.ts:2289

Creates a new BST by mapping each [key, value] pair to a new entry.

Type Parameters

MK

MK = K

New key type.

MV

MV = V

New value type.

MR

MR = any

New raw type.

Parameters

callback

EntryCallback<K, V | undefined, [MK, MV]>

A function to map each [key, value] pair.

options?

Partial<BSTOptions<MK, MV, MR>>

Options for the new BST.

thisArg?

unknown

this context for the callback.

Returns

BST<MK, MV, MR>

A new, mapped BST.

Remarks

Time O(N * H), where N is nodes in this tree, and H is height of the new tree during insertion. Space O(N) for the new tree.

Example

// Transform to new tree
 const bst = new BST<number, number>([[1, 10], [2, 20], [3, 30]]);
    const doubled = bst.map((value, key) => [key, (value ?? 0) * 2] as [number, number]);
    console.log([...doubled.values()]); // [20, 40, 60];

Implementation of

IBinaryTree.map

Overrides

BinaryTree.map

merge()

merge(anotherTree): void;

Defined in: data-structures/binary-tree/binary-tree.ts:897

Merges another tree into this one by seting all its nodes.

Parameters

anotherTree

BinaryTree<K, V, R>

The tree to merge.

Returns

void

Remarks

Time O(N * M), same as setMany, where N is the size of anotherTree and M is the size of this tree. Space O(M) (from set).

Example

// Combine trees
 const t1 = new BinaryTree<number>([1, 2]);
    const t2 = new BinaryTree<number>([3, 4]);
    t1.merge(t2);
    console.log(t1.size); // 4;

Implementation of

IBinaryTree.merge

Inherited from

BinaryTree.merge

morris()

Performs a Morris (threaded) traversal.

Remarks

This traversal uses O(1) extra space (excluding the result array) by temporarily modifying the tree's right child pointers. Time O(N), as each node is visited a constant number of times. Space O(1) (excluding the ans array).

Template

The type of the callback function.

Param

Function to call on each node.

Param

The traversal order ('IN', 'PRE', 'POST').

Param

The node to start from.

Call Signature

morris(): (K | undefined)[];

Defined in: data-structures/binary-tree/binary-tree.ts:2513

Morris traversal (O(1) space)

Returns

(K | undefined)[]

Example

// Morris traversal (O(1) space)
 const tree = new BinaryTree<number>([1, 2, 3]);
    const result = tree.morris(node => node.key, 'IN');
    console.log(result.length); // 3;

Implementation of

IBinaryTree.morris

Inherited from

BinaryTree.morris

Call Signature

morris<C>(
   callback?, 
   pattern?, 
   startNode?): ReturnType<C>[];

Defined in: data-structures/binary-tree/binary-tree.ts:2515

Morris traversal (O(1) space)

Type Parameters

C

C extends NodeCallback<BinaryTreeNode<K, V>>

Parameters

callback?

C

pattern?

DFSOrderPattern

startNode?

Returns

ReturnType<C>[]

Example

// Morris traversal (O(1) space)
 const tree = new BinaryTree<number>([1, 2, 3]);
    const result = tree.morris(node => node.key, 'IN');
    console.log(result.length); // 3;

Implementation of

IBinaryTree.morris

Inherited from

BinaryTree.morris

perfectlyBalance()

perfectlyBalance(iterationType?): boolean;

Defined in: data-structures/binary-tree/bst.ts:2094

Rebuilds the tree to be perfectly balanced.

Parameters

iterationType?

IterationType = ...

The traversal method for the initial node export.

Returns

boolean

True if successful, false if the tree was empty.

Remarks

Time O(N) (O(N) for DFS, O(N) for sorted build). Space O(N) for node array and recursion stack.

Example

// Rebalance the tree
 const bst = new BST<number>();
    // Insert in sorted order (worst case for BST)
    for (let i = 1; i <= 7; i++) bst.add(i);
    console.log(bst.isAVLBalanced()); // false;
    bst.perfectlyBalance();
    console.log(bst.isAVLBalanced()); // true;

print()

print(options?, startNode?): void;

Defined in: data-structures/binary-tree/binary-tree.ts:2870

Prints a visual representation of the tree to the console.

Parameters

options?

BinaryTreePrintOptions

Options to control the output.

startNode?

The node to start printing from.

Returns

void

Remarks

Time O(N) (via toVisual). Space O(N*H) or O(N^2) (via toVisual).

Example

// Display tree
 const tree = new BinaryTree<number>([1, 2, 3]);
    expect(() => tree.print()).not.toThrow();

Inherited from

BinaryTree.print

rangeSearch()

Performs an optimized search for nodes within a given key range.

Remarks

Time O(H + M), where H is tree height and M is the number of matches.

Template

The type of the callback function.

Param

A Range object or a [low, high] tuple.

Param

A function to call on matching nodes.

Param

The node to start the search from.

Param

The traversal method.

Call Signature

rangeSearch(range): (K | undefined)[];

Defined in: data-structures/binary-tree/bst.ts:1135

Find all keys in a range

Parameters

range

Range<K> | [K, K]

Returns

(K | undefined)[]

Example

// Find all keys in a range
 const bst = new BST<number>([10, 20, 30, 40, 50]);
    console.log(bst.rangeSearch([15, 35])); // [20, 30];

Call Signature

rangeSearch<C>(
   range, 
   callback, 
   startNode?, 
   iterationType?): ReturnType<C>[];

Defined in: data-structures/binary-tree/bst.ts:1137

Find all keys in a range

Type Parameters

C

C extends NodeCallback<BSTNode<K, V>>

Parameters

range

Range<K> | [K, K]

callback

C

startNode?

iterationType?

IterationType

Returns

ReturnType<C>[]

Example

// Find all keys in a range
 const bst = new BST<number>([10, 20, 30, 40, 50]);
    console.log(bst.rangeSearch([15, 35])); // [20, 30];

reduce()

reduce<U>(callbackfn, initialValue): U;

Defined in: data-structures/base/iterable-entry-base.ts:171

Reduce entries into a single accumulator.

Type Parameters

U

U

Parameters

callbackfn

ReduceEntryCallback<K, V | undefined, U>

(acc, value, key, index, self) => acc.

initialValue

U

Initial accumulator.

Returns

U

Final accumulator.

Remarks

Time O(n), Space O(1)

Implementation of

IBinaryTree.reduce

Inherited from

BinaryTree.reduce

refill()

refill(keysNodesEntriesOrRaws, values?): void;

Defined in: data-structures/binary-tree/binary-tree.ts:908

Clears the tree and refills it with new items.

Parameters

keysNodesEntriesOrRaws

An iterable of items to set.

values?

Iterable<V | undefined, any, any>

An optional parallel iterable of values.

Returns

void

Remarks

Time O(N) (for clear) + O(N * M) (for setMany) = O(N * M). Space O(M) (from setMany).

Implementation of

IBinaryTree.refill

Inherited from

BinaryTree.refill

search()

Searches the tree for nodes matching a predicate, key, or range.

Remarks

This is an optimized search for a BST. If searching by key or range, it prunes branches. Time O(H + M) for key/range search (H=height, M=matches). O(N) for predicate search. Space O(log N) for the stack.

Template

The type of the callback function.

Param

The key, node, entry, predicate, or range to search for.

Param

If true, stops after finding the first match.

Param

A function to call on matching nodes.

Param

The node to start the search from.

Param

Whether to use 'RECURSIVE' or 'ITERATIVE' search.

Call Signature

search(keyNodeEntryOrPredicate, onlyOne?): (K | undefined)[];

Defined in: data-structures/binary-tree/bst.ts:942

Search nodes by predicate

Parameters

keyNodeEntryOrPredicate

onlyOne?

boolean

Returns

(K | undefined)[]

Example

// Search nodes by predicate
 const bst = new BST<number, string>([[1, 'a'], [2, 'b'], [3, 'c'], [4, 'd']]);
    const found = bst.search(node => node.key > 2, true);
    console.log(found.length); // >= 1;

Implementation of

IBinaryTree.search

Overrides

BinaryTree.search

Call Signature

search<C>(
   keyNodeEntryOrPredicate, 
   onlyOne, 
   callback, 
   startNode?, 
   iterationType?): ReturnType<C>[];

Defined in: data-structures/binary-tree/bst.ts:954

Search nodes by predicate

Type Parameters

C

C extends NodeCallback<BSTNode<K, V>>

Parameters

keyNodeEntryOrPredicate

onlyOne

boolean

callback

C

startNode?

iterationType?

IterationType

Returns

ReturnType<C>[]

Example

// Search nodes by predicate
 const bst = new BST<number, string>([[1, 'a'], [2, 'b'], [3, 'c'], [4, 'd']]);
    const found = bst.search(node => node.key > 2, true);
    console.log(found.length); // >= 1;

Implementation of

IBinaryTree.search

Overrides

BinaryTree.search

set()

set(keyNodeOrEntry, value?): boolean;

Defined in: data-structures/binary-tree/bst.ts:1273

Adds a new node to the BST based on key comparison.

Parameters

keyNodeOrEntry

The key, node, or entry to set.

value?

V

The value, if providing just a key.

Returns

boolean

True if the addition was successful, false otherwise.

Remarks

Time O(log N), where H is tree height. O(N) worst-case (unbalanced tree), O(log N) average. Space O(1).

Example

// Set a key-value pair
 const bst = new BST<number, string>();
    bst.set(1, 'one');
    bst.set(2, 'two');
    console.log(bst.get(1)); // 'one';

Implementation of

IBinaryTree.set

Overrides

BinaryTree.set

setMany()

setMany(
   keysNodesEntriesOrRaws, 
   values?, 
   isBalanceAdd?, 
   iterationType?): boolean[];

Defined in: data-structures/binary-tree/bst.ts:1393

Adds multiple items to the tree.

Parameters

keysNodesEntriesOrRaws

Iterable<R | BTNRep<K, V, BSTNode<K, V>>>

An iterable of items to set.

values?

Iterable<V | undefined, any, any>

An optional parallel iterable of values.

isBalanceAdd?

boolean = true

If true, builds a balanced tree from the items.

iterationType?

IterationType = ...

The traversal method for balanced set (recursive or iterative).

Returns

boolean[]

An array of booleans indicating the success of each individual set operation.

Remarks

If isBalanceAdd is true, sorts the input and builds a balanced tree. Time O(N log N) (due to sort and balanced set). If false, adds items one by one. Time O(N * H), which is O(N^2) worst-case. Space O(N) for sorting and recursion/iteration stack.

Example

// Set multiple key-value pairs
 const bst = new BST<number, string>();
    bst.setMany([[1, 'a'], [2, 'b'], [3, 'c']]);
    console.log(bst.size); // 3;
    console.log(bst.get(2)); // 'b';

Overrides

BinaryTree.setMany

some()

some(predicate, thisArg?): boolean;

Defined in: data-structures/base/iterable-entry-base.ts:83

Test whether any entry satisfies the predicate.

Parameters

predicate

EntryCallback<K, V | undefined, boolean>

(key, value, index, self) => boolean.

thisArg?

unknown

Optional this for callback.

Returns

boolean

true if any passes; otherwise false.

Remarks

Time O(n), Space O(1)

Implementation of

IBinaryTree.some

Inherited from

BinaryTree.some

toArray()

toArray(): [K, V | undefined][];

Defined in: data-structures/base/iterable-entry-base.ts:186

Converts data structure to [key, value] pairs.

Returns

[K, V | undefined][]

Array of entries.

Remarks

Time O(n), Space O(n)

Inherited from

BinaryTree.toArray

toVisual()

toVisual(startNode?, options?): string;

Defined in: data-structures/binary-tree/binary-tree.ts:2801

Generates a string representation of the tree for visualization.

Parameters

startNode?

The node to start printing from.

options?

BinaryTreePrintOptions

Options to control the output (e.g., show nulls).

Returns

string

The string representation of the tree.

Remarks

Time O(N), visits every node. Space O(N*H) or O(N^2) in the worst case, as the string width can grow significantly.

Inherited from

BinaryTree.toVisual

values()

values(): IterableIterator<V | undefined>;

Defined in: data-structures/base/iterable-entry-base.ts:53

Iterate over values only.

Returns

IterableIterator<V | undefined>

Iterator of values.

Remarks

Time O(n), Space O(1)

Implementation of

IBinaryTree.values

Inherited from

BinaryTree.values

Protected Members

_comparator

protected readonly _comparator: Comparator<K>;

Defined in: data-structures/binary-tree/bst.ts:372

The comparator function used to determine the order of keys in the tree.

Remarks

Time O(1) Space O(1)

_DEFAULT_NODE_CALLBACK

protected readonly _DEFAULT_NODE_CALLBACK: NodeCallback<BinaryTreeNode<K, V> | null | undefined, K | undefined>;

Defined in: data-structures/binary-tree/binary-tree.ts:3066

(Protected) Default callback function, returns the node's key.

Remarks

Time O(1)

Param

The node.

Returns

The node's key or undefined.

Inherited from

BinaryTree._DEFAULT_NODE_CALLBACK

Accessors

_bound()

protected _bound(
   keyNodeEntryOrPredicate, 
   isLower, 
   iterationType): BSTNode<K, V> | undefined;

Defined in: data-structures/binary-tree/bst.ts:2643

(Protected) Core bound search implementation supporting all parameter types. Unified logic for both lowerBound and upperBound. Resolves various input types (Key, Node, Entry, Predicate) using parent class utilities.

Parameters

keyNodeEntryOrPredicate

The key, node, entry, or predicate function to search for.

isLower

boolean

True for lowerBound (>=), false for upperBound (>).

iterationType

IterationType

The iteration type (RECURSIVE or ITERATIVE).

Returns

BSTNode<K, V> | undefined

The first matching node, or undefined if no such node exists.

_boundByKey()

protected _boundByKey(
   key, 
   isLower, 
   iterationType): BSTNode<K, V> | undefined;

Defined in: data-structures/binary-tree/bst.ts:2700

(Protected) Binary search for bound by key with pruning optimization. Performs standard BST binary search, choosing left or right subtree based on comparator result. For lowerBound: finds first node where key >= target. For upperBound: finds first node where key > target.

Parameters

key

K

The target key to search for.

isLower

boolean

True for lowerBound (>=), false for upperBound (>).

iterationType

IterationType

The iteration type (RECURSIVE or ITERATIVE).

Returns

BSTNode<K, V> | undefined

The first node matching the bound condition, or undefined if none exists.

_boundByPredicate()

protected _boundByPredicate(predicate, iterationType): BSTNode<K, V> | undefined;

Defined in: data-structures/binary-tree/bst.ts:2755

(Protected) In-order traversal search by predicate. Falls back to linear in-order traversal when predicate-based search is required. Returns the first node that satisfies the predicate function. Note: Predicate-based search cannot leverage BST's binary search optimization. Time Complexity: O(n) since it may visit every node.

Parameters

predicate

NodePredicate<BSTNode<K, V>>

The predicate function to test nodes.

iterationType

IterationType

The iteration type (RECURSIVE or ITERATIVE).

Returns

BSTNode<K, V> | undefined

The first node satisfying predicate, or undefined if none found.

_clearNodes()

protected _clearNodes(): void;

Defined in: data-structures/binary-tree/binary-tree.ts:3500

(Protected) Clears all nodes from the tree.

Returns

void

Remarks

Time O(1)

Inherited from

BinaryTree._clearNodes

_clearValues()

protected _clearValues(): void;

Defined in: data-structures/binary-tree/binary-tree.ts:3509

(Protected) Clears all values from the external store.

Returns

void

Remarks

Time O(N)

Inherited from

BinaryTree._clearValues

_clone()

protected _clone(cloned): void;

Defined in: data-structures/binary-tree/binary-tree.ts:3159

(Protected) Helper for cloning. Performs a BFS and sets all nodes to the new tree.

Parameters

cloned

BinaryTree<K, V, R>

The new, empty tree instance to populate.

Returns

void

Remarks

Time O(N * M) (O(N) BFS + O(M) set for each node).

Inherited from

BinaryTree._clone

_compare()

protected _compare(a, b): number;

Defined in: data-structures/binary-tree/bst.ts:2895

(Protected) Compares two keys using the tree's comparator and reverse setting.

Parameters

a

K

The first key.

b

K

The second key.

Returns

number

A number (1, -1, or 0) representing the comparison.

Remarks

Time O(1) Space O(1)

_createDefaultComparator()

protected _createDefaultComparator(): Comparator<K>;

Defined in: data-structures/binary-tree/bst.ts:2368

(Protected) Creates the default comparator function for keys that don't have a custom comparator.

Returns

Comparator<K>

The default comparator function.

Remarks

Time O(1) Space O(1)

_createInstance()

protected _createInstance<TK, TV, TR>(options?): this;

Defined in: data-structures/binary-tree/bst.ts:2817

(Protected) Creates a new, empty instance of the same BST constructor.

Type Parameters

TK

TK = K

TV

TV = V

TR

TR = R

Parameters

options?

Partial<BSTOptions<TK, TV, TR>>

Options for the new BST.

Returns

this

A new, empty BST.

Remarks

Time O(1)

Overrides

BinaryTree._createInstance

_createLike()

protected _createLike<TK, TV, TR>(iter?, options?): BST<TK, TV, TR>;

Defined in: data-structures/binary-tree/bst.ts:2834

(Protected) Creates a new instance of the same BST constructor, potentially with different generic types.

Type Parameters

TK

TK = K

TV

TV = V

TR

TR = R

Parameters

iter?

An iterable to populate the new BST.

options?

Partial<BSTOptions<TK, TV, TR>>

Options for the new BST.

Returns

BST<TK, TV, TR>

A new BST.

Remarks

Time O(N log N) or O(N^2) (from constructor) due to processing the iterable.

Overrides

BinaryTree._createLike

_deleteByKey()

protected _deleteByKey(key): boolean;

Defined in: data-structures/binary-tree/bst.ts:2906

(Private) Deletes a node by its key.

Parameters

key

K

The key of the node to delete.

Returns

boolean

True if the node was found and deleted, false otherwise.

Remarks

Standard BST deletion algorithm. Time O(log N), O(N) worst-case. Space O(1).

_dfs()

protected _dfs<C>(
   callback, 
   pattern?, 
   onlyOne?, 
   startNode?, 
   iterationType?, 
   includeNull?, 
   shouldVisitLeft?, 
   shouldVisitRight?, 
   shouldVisitRoot?, 
   shouldProcessRoot?): ReturnType<C>[];

Defined in: data-structures/binary-tree/binary-tree.ts:2877

Type Parameters

C

C extends NodeCallback<BinaryTreeNode<K, V>>

Callback type.

Parameters

callback

C

Function to call on nodes.

pattern?

DFSOrderPattern

Traversal order.

onlyOne?

boolean

Stop after first match.

startNode?

Starting node.

iterationType?

IterationType

Traversal method.

includeNull?

boolean

Include nulls.

shouldVisitLeft?

(node) => boolean

Predicate to traverse left.

shouldVisitRight?

(node) => boolean

Predicate to traverse right.

shouldVisitRoot?

(node) => boolean

Predicate to visit root.

shouldProcessRoot?

(node) => boolean

Predicate to process root.

Returns

ReturnType<C>[]

Array of callback results.

Inherited from

BinaryTree._dfs

_displayAux()

protected _displayAux(node, options): NodeDisplayLayout;

Defined in: data-structures/binary-tree/binary-tree.ts:3183

(Protected) Recursive helper for toVisual.

Parameters

node

BinaryTreeNode<K, V> | null | undefined

The current node.

options

BinaryTreePrintOptions

Print options.

Returns

NodeDisplayLayout

Layout information for this subtree.

Remarks

Time O(N), Space O(N*H) or O(N^2)

Inherited from

BinaryTree._displayAux

_ensurePredicate()

protected _ensurePredicate(keyNodeEntryOrPredicate): NodePredicate<BinaryTreeNode<K, V>>;

Defined in: data-structures/binary-tree/binary-tree.ts:3406

(Protected) Converts a key, node, entry, or predicate into a standardized predicate function.

Parameters

keyNodeEntryOrPredicate

The item to convert.

Returns

NodePredicate<BinaryTreeNode<K, V>>

A predicate function.

Remarks

Time O(1)

Inherited from

BinaryTree._ensurePredicate

_extractKey()

protected _extractKey(keyNodeOrEntry): K | null | undefined;

Defined in: data-structures/binary-tree/binary-tree.ts:3466

(Protected) Extracts the key from a key, node, or entry.

Parameters

keyNodeOrEntry

The item.

Returns

K | null | undefined

The extracted key.

Remarks

Time O(1)

Inherited from

BinaryTree._extractKey

_floorByKey()

protected _floorByKey(key, iterationType): BSTNode<K, V> | undefined;

Defined in: data-structures/binary-tree/bst.ts:2408

(Protected) Binary search for floor by key with pruning optimization. Performs standard BST binary search, choosing left or right subtree based on comparator result. Finds first node where key <= target.

Parameters

key

K

The target key to search for.

iterationType

IterationType

The iteration type (RECURSIVE or ITERATIVE).

Returns

BSTNode<K, V> | undefined

The first node with key <= target, or undefined if none exists.

Remarks

Time O(h) where h is tree height.

_floorByPredicate()

protected _floorByPredicate(predicate, iterationType): BSTNode<K, V> | undefined;

Defined in: data-structures/binary-tree/bst.ts:2461

(Protected) In-order traversal search for floor by predicate. Falls back to linear in-order traversal when predicate-based search is required. Returns the last node that satisfies the predicate function.

Parameters

predicate

NodePredicate<BSTNode<K, V>>

The predicate function to test nodes.

iterationType

IterationType

The iteration type (RECURSIVE or ITERATIVE).

Returns

BSTNode<K, V> | undefined

The last node satisfying predicate (highest key), or undefined if none found.

Remarks

Time Complexity: O(n) since it may visit every node. Space Complexity: O(h) for recursion, O(h) for iterative stack.

_getIterator()

protected _getIterator(node?): IterableIterator<[K, V | undefined]>;

Defined in: data-structures/binary-tree/binary-tree.ts:3022

(Protected) Gets the iterator for the tree (default in-order).

Parameters

node?

BinaryTreeNode<K, V> | null

The node to start iteration from.

Returns

IterableIterator<[K, V | undefined]>

An iterator for [key, value] pairs.

Remarks

Time O(N) for full iteration. O(H) to get the first element. Space O(H) for the iterative stack. O(H) for recursive stack.

Inherited from

BinaryTree._getIterator

_isDisplayLeaf()

protected _isDisplayLeaf(node, options): boolean;

Defined in: data-structures/binary-tree/binary-tree.ts:3278

Check if a node is a display leaf (empty, null, undefined, NIL, or real leaf).

Parameters

node

BinaryTreeNode<K, V> | null | undefined

options

BinaryTreePrintOptions

Returns

boolean

Inherited from

BinaryTree._isDisplayLeaf

_isPredicate()

protected _isPredicate(p): p is NodePredicate<BinaryTreeNode<K, V>>;

Defined in: data-structures/binary-tree/binary-tree.ts:3455

(Protected) Checks if an item is a predicate function.

Parameters

p

unknown

The item to check.

Returns

p is NodePredicate<BinaryTreeNode<K, V>>

True if it's a function.

Remarks

Time O(1)

Inherited from

BinaryTree._isPredicate

_keyValueNodeOrEntryToNodeAndValue()

protected _keyValueNodeOrEntryToNodeAndValue(keyNodeOrEntry, value?): [OptNode<BSTNode<K, V>>, V | undefined];

Defined in: data-structures/binary-tree/bst.ts:2867

(Protected) Converts a key, node, or entry into a standardized [node, value] tuple.

Parameters

keyNodeOrEntry

The input item.

value?

V

An optional value (used if input is just a key).

Returns

[OptNode<BSTNode<K, V>>, V | undefined]

A tuple of [node, value].

Remarks

Time O(1)

Overrides

BinaryTree._keyValueNodeOrEntryToNodeAndValue

_lowerByKey()

protected _lowerByKey(key, iterationType): BSTNode<K, V> | undefined;

Defined in: data-structures/binary-tree/bst.ts:2526

(Protected) Binary search for lower by key with pruning optimization. Performs standard BST binary search, choosing left or right subtree based on comparator result. Finds first node where key < target.

Parameters

key

K

The target key to search for.

iterationType

IterationType

The iteration type (RECURSIVE or ITERATIVE).

Returns

BSTNode<K, V> | undefined

The first node with key < target, or undefined if none exists.

Remarks

Time O(h) where h is tree height.

_lowerByPredicate()

protected _lowerByPredicate(predicate, iterationType): BSTNode<K, V> | undefined;

Defined in: data-structures/binary-tree/bst.ts:2579

(Protected) In-order traversal search for lower by predicate. Falls back to linear in-order traversal when predicate-based search is required. Returns the node that satisfies the predicate and appears last in in-order traversal.

Parameters

predicate

NodePredicate<BSTNode<K, V>>

The predicate function to test nodes.

iterationType

IterationType

The iteration type (RECURSIVE or ITERATIVE).

Returns

BSTNode<K, V> | undefined

The last node satisfying predicate (highest key < target), or undefined if none found.

Remarks

Time Complexity: O(n) since it may visit every node. Space Complexity: O(h) for recursion, O(h) for iterative stack.

_replaceNode()

protected _replaceNode(oldNode, newNode): BinaryTreeNode<K, V>;

Defined in: data-structures/binary-tree/binary-tree.ts:3368

(Protected) Replaces a node in the tree with a new node, maintaining children and parent links.

Parameters

oldNode

BinaryTreeNode<K, V>

The node to be replaced.

newNode

BinaryTreeNode<K, V>

The node to insert.

Returns

BinaryTreeNode<K, V>

The newNode.

Remarks

Time O(1)

Inherited from

BinaryTree._replaceNode

_resolveDisplayLeaf()

protected _resolveDisplayLeaf(
   node, 
   options, 
   emptyDisplayLayout): NodeDisplayLayout;

Defined in: data-structures/binary-tree/binary-tree.ts:3308

Resolve a display leaf node to its layout.

Parameters

node

BinaryTreeNode<K, V> | null | undefined

options

BinaryTreePrintOptions

emptyDisplayLayout

NodeDisplayLayout

Returns

NodeDisplayLayout

Inherited from

BinaryTree._resolveDisplayLeaf

_setRoot()

protected _setRoot(v): void;

Defined in: data-structures/binary-tree/bst.ts:2882

(Protected) Sets the root node and clears its parent reference.

Parameters

v

OptNode<BSTNode<K, V>>

The node to set as root.

Returns

void

Remarks

Time O(1)

Overrides

BinaryTree._setRoot

_setValue()

protected _setValue(key, value): boolean;

Defined in: data-structures/binary-tree/binary-tree.ts:3487

(Protected) Sets a value in the external store (Map mode).

Parameters

key

K | null | undefined

The key.

value

V | undefined

The value.

Returns

boolean

True if successful.

Remarks

Time O(1) (average for Map.set).

Inherited from

BinaryTree._setValue

_snapshotOptions()

protected _snapshotOptions<TK, TV, TR>(): BSTOptions<TK, TV, TR>;

Defined in: data-structures/binary-tree/bst.ts:2852

(Protected) Snapshots the current BST's configuration options.

Type Parameters

TK

TK = K

TV

TV = V

TR

TR = R

Returns

BSTOptions<TK, TV, TR>

The options object.

Remarks

Time O(1)

Overrides

BinaryTree._snapshotOptions

_swapProperties()

protected _swapProperties(srcNode, destNode): BinaryTreeNode<K, V> | undefined;

Defined in: data-structures/binary-tree/binary-tree.ts:3334

(Protected) Swaps the key/value properties of two nodes.

Parameters

srcNode

The source node.

destNode

The destination node.

Returns

BinaryTreeNode<K, V> | undefined

The destNode (now holding srcNode's properties).

Remarks

Time O(1)

Inherited from

BinaryTree._swapProperties

Class: BST<K, V, R>

Examples​

Extends​

Extended by​

Type Parameters​

K​

V​

R​

Implements​

Constructors​

Constructor​

Parameters​

keysNodesEntriesOrRaws?​

options?​

Returns​

Remarks​

Overrides​

Properties​

comparator​

Get Signature​

Remarks​

Returns​

isDuplicate​

Get Signature​

Remarks​

Returns​

Implementation of​

Inherited from​

isMapMode​

Get Signature​

Remarks​

Returns​

Implementation of​

Inherited from​

NIL​

Get Signature​

Remarks​

Returns​

Implementation of​

Inherited from​

root​

Get Signature​

Remarks​

Returns​

Implementation of​

Overrides​

size​

Get Signature​

Remarks​

Returns​

Implementation of​

Inherited from​

store​

Get Signature​

Remarks​

Returns​

Implementation of​

Inherited from​

toEntryFn​

Get Signature​

Remarks​

Returns​

Implementation of​

Inherited from​

Methods​

[iterator]()​

Parameters​

args​

Returns​

Remarks​

Implementation of​

Inherited from​

add()​

Parameters​

keyNodeOrEntry​

Returns​

Remarks​

Example​

Implementation of​

Inherited from​

Examples

Extends

Extended by

Type Parameters

K

V

R

Implements

Constructors

Constructor

Parameters

keysNodesEntriesOrRaws?

options?

Returns

Remarks

Overrides

Properties

comparator

Get Signature

Remarks

Returns

isDuplicate

Get Signature

Remarks

Returns

Implementation of

Inherited from

isMapMode

Get Signature

Remarks

Returns

Implementation of

Inherited from

NIL

Get Signature

Remarks

Returns

Implementation of

Inherited from

root

Get Signature

Remarks

Returns

Implementation of

Overrides

size

Get Signature

Remarks

Returns

Implementation of

Inherited from

store

Get Signature

Remarks

Returns

Implementation of

Inherited from

toEntryFn

Get Signature

Remarks

Returns

Implementation of

Inherited from

Methods

[iterator]()

Parameters

args

Returns

Remarks

Implementation of

Inherited from

add()

Parameters

keyNodeOrEntry

Returns

Remarks

Example

Implementation of

Inherited from

addMany()