RedBlackTree

Class: RedBlackTree<K, V, R>

Defined in: data-structures/binary-tree/red-black-tree.ts:254

Represents a Red-Black Tree (self-balancing BST) supporting map-like mode and stable O(log n) updates.

Remarks

Operation complexity depends on the method; see each method's docs.

Examples

// Red-Black Tree with key-value pairs for lookups
 interface Employee {
      id: number;
      name: string;
    }

    // Create tree with employee data
    const employees = new RedBlackTree<number, Employee>([
      [1, { id: 1, name: 'Alice' }],
      [3, { id: 3, name: 'Charlie' }],
      [2, { id: 2, name: 'Bob' }]
    ]);

    // Retrieve employee by ID
    const alice = employees.get(1);
    console.log(alice?.name); // 'Alice';

    // Verify sorted order by ID
    console.log([...employees.keys()]); // [1, 2, 3];

// Red-Black Tree range search for filtering
 interface Product {
      name: string;
      price: number;
    }

    const products = new RedBlackTree<number, Product>([
      [10, { name: 'Item A', price: 10 }],
      [25, { name: 'Item B', price: 25 }],
      [40, { name: 'Item C', price: 40 }],
      [50, { name: 'Item D', price: 50 }]
    ]);

    // Find products in price range [20, 45]
    const pricesInRange = products.rangeSearch([20, 45], node => {
      return products.get(node)?.name;
    });

    console.log(pricesInRange); // ['Item B', 'Item C'];

// Red-Black Tree as database index for stock market data
 interface StockPrice {
      symbol: string;
      volume: number;
      timestamp: Date;
    }

    // Simulate real-time stock price index
    const priceIndex = new RedBlackTree<number, StockPrice>([
      [142.5, { symbol: 'AAPL', volume: 1000000, timestamp: new Date() }],
      [335.2, { symbol: 'MSFT', volume: 800000, timestamp: new Date() }],
      [3285.04, { symbol: 'AMZN', volume: 500000, timestamp: new Date() }],
      [267.98, { symbol: 'META', volume: 750000, timestamp: new Date() }],
      [234.57, { symbol: 'GOOGL', volume: 900000, timestamp: new Date() }]
    ]);

    // Find highest-priced stock
    const maxPrice = priceIndex.getRightMost();
    console.log(priceIndex.get(maxPrice)?.symbol); // 'AMZN';

    // Find stocks in price range [200, 400] for portfolio balancing
    const stocksInRange = priceIndex.rangeSearch([200, 400], node => {
      const stock = priceIndex.get(node);
      return {
        symbol: stock?.symbol,
        price: node,
        volume: stock?.volume
      };
    });

    console.log(stocksInRange.length); // 3;
    console.log(stocksInRange.some((s: any) => s.symbol === 'GOOGL')); // true;
    console.log(stocksInRange.some((s: any) => s.symbol === 'META')); // true;
    console.log(stocksInRange.some((s: any) => s.symbol === 'MSFT')); // true;

Extends

BST<K, V, R>

Type Parameters

K

K = any

V

V = any

R

R = any

Efficient self-balancing, but not completely balanced. Compared with AVLTree, the addition and deletion efficiency is high, but the query efficiency is slightly lower.
It is BST itself. Compared with Heap which is not completely ordered, RedBlackTree is completely ordered.

Implements

IBinaryTree<K, V, R>

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.

Inherited from

BST.comparator

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

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

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

BST.NIL

root

Get Signature

get root(): RedBlackTreeNode<K, V> | undefined;

Defined in: data-structures/binary-tree/red-black-tree.ts:305

Get the current root node.

Remarks

Time O(1), Space O(1)

Returns

RedBlackTreeNode<K, V> | undefined

Root node, or undefined.

Implementation of

IBinaryTree.root

Overrides

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

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

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

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

BST.[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

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

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

Inherited from

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

Inherited from

BST.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;

Inherited from

BST.ceiling

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>

Inherited from

BST.ceiling

clear()

clear(): void;

Defined in: data-structures/binary-tree/red-black-tree.ts:476

Remove all nodes and clear internal caches.

Returns

void

Remarks

Time O(n) average, Space O(1)

Example

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

Implementation of

IBinaryTree.clear

Overrides

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

BST.clone

createNode()

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

Defined in: data-structures/binary-tree/red-black-tree.ts:317

Create a red-black node for the given key/value (value ignored in map mode).

Parameters

key

K

See parameter type for details.

value?

V

See parameter type for details.

color?

RBTNColor = 'BLACK'

See parameter type for details.

Returns

RedBlackTreeNode<K, V>

A new RedBlackTreeNode instance.

Remarks

Time O(1), Space O(1)

Implementation of

IBinaryTree.createNode

Overrides

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

BST.createTree

delete()

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

Defined in: data-structures/binary-tree/red-black-tree.ts:1211

Delete a node by key/node/entry and rebalance as needed.

Parameters

keyNodeEntryRawOrPredicate

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

Key, node, or [key, value] entry identifying the node to delete.

Returns

BinaryTreeDeleteResult<RedBlackTreeNode<K, V>>[]

Array with deletion metadata (removed node, rebalancing hint if any).

Remarks

Time O(log n) average, Space O(1)

Example

// Remove and rebalance
 const rbt = new RedBlackTree<number>([10, 5, 15, 3, 7]);
    rbt.delete(5);
    console.log(rbt.has(5)); // false;
    console.log(rbt.size); // 4;

Implementation of

IBinaryTree.delete

Overrides

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

Inherited from

BST.deleteWhere

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

Inherited from

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

Inherited from

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

Inherited from

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

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

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

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

BST.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;

Inherited from

BST.floor

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>

Inherited from

BST.floor

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

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

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

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

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

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

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

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

Inherited from

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

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

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

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

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

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

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

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

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

BST.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;

Inherited from

BST.higher

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>

Inherited from

BST.higher

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;

Inherited from

BST.isAVLBalanced

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

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

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

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

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

BST.isNIL

isNode()

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

Defined in: data-structures/binary-tree/red-black-tree.ts:328

Type guard: check whether the input is a RedBlackTreeNode.

Parameters

keyNodeOrEntry

See parameter type for details.

Returns

keyNodeOrEntry is RedBlackTreeNode<K, V>

True if the value is a RedBlackTreeNode.

Remarks

Time O(1), Space O(1)

Overrides

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

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

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

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

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

BST.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)

Inherited from

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

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

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

BST.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)[]

Inherited from

BST.lesserOrGreaterTraverse

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>[]

Inherited from

BST.lesserOrGreaterTraverse

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

Inherited from

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

Inherited from

BST.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;

Inherited from

BST.lower

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>

Inherited from

BST.lower

map()

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

Defined in: data-structures/binary-tree/red-black-tree.ts:1561

Transform to new tree

Type Parameters

MK

MK = K

MV

MV = V

MR

MR = any

Parameters

callback

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

options?

Partial<RedBlackTreeOptions<MK, MV, MR>>

thisArg?

unknown

Returns

RedBlackTree<MK, MV, MR>

Example

// Transform to new tree
 const rbt = new RedBlackTree<number, number>([[1, 10], [2, 20]]);
    const doubled = rbt.map((v, k) => [k, (v ?? 0) * 2] as [number, number]);
    console.log([...doubled.values()]); // [20, 40];

Implementation of

IBinaryTree.map

Overrides

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

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

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

BST.morris

perfectlyBalance()

perfectlyBalance(_iterationType?): boolean;

Defined in: data-structures/binary-tree/red-black-tree.ts:1412

Red-Black trees are self-balancing — perfectlyBalance rebuilds via sorted bulk insert, which naturally produces a balanced RBT.

Parameters

_iterationType?

IterationType

Returns

boolean

Remarks

Time O(N), Space O(N)

Example

// Rebalance tree
 const rbt = new RedBlackTree<number>([1, 2, 3, 4, 5]);
    rbt.perfectlyBalance();
    console.log(rbt.isAVLBalanced()); // true;

Overrides

BST.perfectlyBalance

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

BST.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];

Inherited from

BST.rangeSearch

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];

Inherited from

BST.rangeSearch

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

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

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

Inherited from

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

Inherited from

BST.search

set()

set(keyNodeOrEntry, value?): boolean;

Defined in: data-structures/binary-tree/red-black-tree.ts:1014

Insert or update a key/value (map mode) or key-only (set mode).

This method is optimized for:

monotonic inserts via min/max boundary fast paths
updates via a single-pass search (no double walk)

Parameters

keyNodeOrEntry

value?

V

Returns

boolean

Remarks

Time O(log n) average, Space O(1)

Example

// basic Red-Black Tree with simple number keys
 // Create a simple Red-Black Tree with numeric keys
    const tree = new RedBlackTree([5, 2, 8, 1, 9]);

    tree.print();
    //   _2___
    //  /     \
    //  1    _8_
    //      /   \
    //      5   9

    // Verify the tree maintains sorted order
    console.log([...tree.keys()]); // [1, 2, 5, 8, 9];

    // Check size
    console.log(tree.size); // 5;

Implementation of

IBinaryTree.set

Overrides

BST.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';

Inherited from

BST.setMany

setWithHint()

setWithHint(
   key, 
   value, 
   hint?): boolean;

Defined in: data-structures/binary-tree/red-black-tree.ts:856

Boolean wrapper for setWithHintNode.

Parameters

key

K

value

V

hint?

RedBlackTreeNode<K, V>

Returns

boolean

Remarks

Time O(log n) average, Space O(1)

setWithHintNode()

setWithHintNode(
   key, 
   value, 
   hint?): RedBlackTreeNode<K, V> | undefined;

Defined in: data-structures/binary-tree/red-black-tree.ts:756

Insert/update using a hint node to speed up nearby insertions.

close to the expected insertion position (often the previously returned node in a loop).

When the hint is a good fit (sorted / nearly-sorted insertion), this can avoid most of the normal root-to-leaf search and reduce constant factors.

When the hint does not match (random workloads), this will fall back to the normal set path.

Parameters

key

K

value

V

hint?

RedBlackTreeNode<K, V>

Returns

RedBlackTreeNode<K, V> | undefined

Remarks

Time O(log n) average, Space O(1)

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

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

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

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

BST.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)

Inherited from

BST._comparator

_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

BST._DEFAULT_NODE_CALLBACK

_header

protected _header: RedBlackTreeNode<K, V>;

Defined in: data-structures/binary-tree/red-black-tree.ts:291

(Internal) Header sentinel:

header.parent -> root
header._left -> min (or NIL)
header._right -> max (or NIL)

IMPORTANT:

This header is NOT part of the actual tree.
Do NOT use header.left / header.right accessors for wiring: those setters update NIL.parent and can corrupt sentinel invariants / cause hangs. Only touch header._left/_right.

_minNode

protected _minNode: RedBlackTreeNode<K, V> | undefined;

Defined in: data-structures/binary-tree/red-black-tree.ts:297

(Internal) Cache of the current minimum and maximum nodes. Used for fast-path insert/update when keys are monotonic or near-boundary.

Accessors

_attachNewNode()

protected _attachNewNode(
   parent, 
   side, 
   node): void;

Defined in: data-structures/binary-tree/red-black-tree.ts:557

(Internal) Attach a new node directly under a known parent/side (no search).

This is a performance-oriented helper used by boundary fast paths and hinted insertion. It will:

wire parent/child pointers (using accessors, so parent pointers are updated)
initialize children to NIL
mark the new node RED, then run insert fix-up

Precondition: the chosen slot (parent.left/parent.right) is empty (NIL/null/undefined).

Parameters

parent

RedBlackTreeNode<K, V>

side

"right" | "left"

node

RedBlackTreeNode<K, V>

Returns

void

Remarks

Time O(log n) average, Space O(1)

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

Inherited from

BST._bound

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

Inherited from

BST._boundByKey

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

Inherited from

BST._boundByPredicate

_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

BST._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

BST._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

BST._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)

Inherited from

BST._compare

_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)

Inherited from

BST._createDefaultComparator

_createInstance()

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

Defined in: data-structures/binary-tree/red-black-tree.ts:1579

(Internal) Create an empty instance of the same concrete tree type.

Type Parameters

TK

TK = K

TV

TV = V

TR

TR = R

Parameters

options?

Partial<RedBlackTreeOptions<TK, TV, TR>>

Returns

this

Remarks

Time O(1) average, Space O(1)

Overrides

BST._createInstance

_createLike()

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

Defined in: data-structures/binary-tree/red-black-tree.ts:1591

(Internal) Create a like-kind tree (same concrete class) populated from an iterable.

Type Parameters

TK

TK = K

TV

TV = V

TR

TR = R

Parameters

iter?

options?

Partial<RedBlackTreeOptions<TK, TV, TR>>

Returns

RedBlackTree<TK, TV, TR>

Remarks

Time O(m log m) average (m = iterable length), Space O(m)

Overrides

BST._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).

Inherited from

BST._deleteByKey

_deleteFixup()

protected _deleteFixup(node): void;

Defined in: data-structures/binary-tree/red-black-tree.ts:1773

(Protected) Restore red-black properties after deletion (recolor/rotate).

Parameters

node

RedBlackTreeNode<K, V> | undefined

Child that replaced the deleted node (may be undefined).

Returns

void

void

Remarks

Time O(log n) average, 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

BST._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

BST._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

BST._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

BST._extractKey

_findNodeByKey()

protected _findNodeByKey(key): RedBlackTreeNode<K, V> | undefined;

Defined in: data-structures/binary-tree/red-black-tree.ts:491

(Internal) Find a node by key using a tight BST walk (no allocations).

NOTE: This uses header.parent as the canonical root pointer.

Parameters

key

K

Returns

RedBlackTreeNode<K, V> | undefined

Remarks

Time O(log n) average, Space O(1)

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

Inherited from

BST._floorByKey

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

Inherited from

BST._floorByPredicate

_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

BST._getIterator

_insert()

protected _insert(node): CRUD;

Defined in: data-structures/binary-tree/red-black-tree.ts:1638

(Protected) Standard BST insert followed by red-black fix-up.

Parameters

node

RedBlackTreeNode<K, V>

Node to insert.

Returns

CRUD

Status string: 'CREATED' or 'UPDATED'.

Remarks

Time O(log n) average, Space O(1)

_insertFixup()

protected _insertFixup(z): void;

Defined in: data-structures/binary-tree/red-black-tree.ts:1704

(Protected) Restore red-black properties after insertion (recolor/rotate).

Parameters

z

RedBlackTreeNode<K, V> | undefined

Recently inserted node.

Returns

void

void

Remarks

Time O(log n) average, Space O(1)

_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

BST._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

BST._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)

Inherited from

BST._keyValueNodeOrEntryToNodeAndValue

_leftRotate()

protected _leftRotate(x): void;

Defined in: data-structures/binary-tree/red-black-tree.ts:1852

(Protected) Perform a left rotation around x.

Parameters

x

RedBlackTreeNode<K, V> | undefined

Pivot node to rotate around.

Returns

void

void

Remarks

Time O(1), Space O(1)

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

Inherited from

BST._lowerByKey

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

Inherited from

BST._lowerByPredicate

_predecessorOf()

protected _predecessorOf(node): RedBlackTreeNode<K, V> | undefined;

Defined in: data-structures/binary-tree/red-black-tree.ts:509

(Internal) In-order predecessor of a node in a BST.

Parameters

node

RedBlackTreeNode<K, V>

Returns

RedBlackTreeNode<K, V> | undefined

Remarks

Time O(log n) average, Space O(1)

_replaceNode()

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

Defined in: data-structures/binary-tree/red-black-tree.ts:1623

(Internal) Replace a node in place while preserving its color.

Parameters

oldNode

RedBlackTreeNode<K, V>

newNode

RedBlackTreeNode<K, V>

Returns

RedBlackTreeNode<K, V>

Remarks

Time O(1) average, Space O(1)

Overrides

BST._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

BST._resolveDisplayLeaf

_rightRotate()

protected _rightRotate(y): void;

Defined in: data-structures/binary-tree/red-black-tree.ts:1884

(Protected) Perform a right rotation around y.

Parameters

y

RedBlackTreeNode<K, V> | undefined

Pivot node to rotate around.

Returns

void

void

Remarks

Time O(1), Space O(1)

_setKV()

protected _setKV(key, nextValue?): boolean;

Defined in: data-structures/binary-tree/red-black-tree.ts:732

(Internal) Boolean wrapper around _setKVNode.

Includes a map-mode update fast-path:

If isMapMode=true and the key already exists in _store, then updating the value does not require any tree search/rotation (tree shape depends only on key).
This path is intentionally limited to nextValue !== undefined to preserve existing semantics for undefined values.

Parameters

key

K

nextValue?

V

Returns

boolean

Remarks

Time O(log n) average, Space O(1)

_setKVNode()

protected _setKVNode(key, nextValue?): 
  | {
  created: boolean;
  node: RedBlackTreeNode<K, V>;
}
  | undefined;

Defined in: data-structures/binary-tree/red-black-tree.ts:606

(Internal) Core set implementation returning the affected node.

Hot path goals:

Avoid double walks (search+insert): do a single traversal that either updates or inserts.
Use header min/max caches to fast-path boundary inserts.
Keep header._left/_right as canonical min/max pointers.

Return value:

{ node, created:false } when an existing key is updated
{ node, created:true } when a new node is inserted
undefined only on unexpected internal failure.

Parameters

key

K

nextValue?

V

Returns

| { created: boolean; node: RedBlackTreeNode<K, V>; } | undefined

Remarks

Time O(log n) average, Space O(1)

_setMaxCache()

protected _setMaxCache(node): void;

Defined in: data-structures/binary-tree/red-black-tree.ts:587

(Internal) Update max cache pointers (header._right is the canonical max pointer).

Parameters

node

RedBlackTreeNode<K, V> | undefined

Returns

void

Remarks

Time O(1), Space O(1)

_setMinCache()

protected _setMinCache(node): void;

Defined in: data-structures/binary-tree/red-black-tree.ts:578

(Internal) Update min cache pointers (header._left is the canonical min pointer).

Parameters

node

RedBlackTreeNode<K, V> | undefined

Returns

void

Remarks

Time O(1), Space O(1)

_setRoot()

protected _setRoot(v): void;

Defined in: data-structures/binary-tree/red-black-tree.ts:1608

(Internal) Set the root pointer and keep header.parent in sync.

Parameters

v

RedBlackTreeNode<K, V> | undefined

Returns

void

Remarks

Time O(1), Space O(1)

Overrides

BST._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

BST._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)

Inherited from

BST._snapshotOptions

_successorOf()

protected _successorOf(node): RedBlackTreeNode<K, V> | undefined;

Defined in: data-structures/binary-tree/red-black-tree.ts:529

(Internal) In-order successor of a node in a BST.

Parameters

node

RedBlackTreeNode<K, V>

Returns

RedBlackTreeNode<K, V> | undefined

Remarks

Time O(log n) average, Space O(1)

_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

BST._swapProperties

_transplant()

protected _transplant(u, v): void;

Defined in: data-structures/binary-tree/red-black-tree.ts:1684

(Protected) Transplant a subtree in place of another during deletion.

Parameters

u

RedBlackTreeNode<K, V>

Node to replace.

v

RedBlackTreeNode<K, V> | undefined

Replacement subtree root (may be undefined).

Returns

void

void

Remarks

Time O(1), Space O(1)

Class: RedBlackTree<K, V, R>

Remarks​

Examples​

Extends​

Type Parameters​

K​

V​

R​

Implements​

Properties​

comparator​

Get Signature​

Remarks​

Returns​

Inherited from​

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

Parameters​

keysNodesEntriesOrRaws​

Returns​

Remarks​

Example​

Implementation of​

Remarks

Examples

Extends

Type Parameters

K

V

R

Implements

Properties

comparator

Get Signature

Remarks

Returns

Inherited from

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

Parameters

keysNodesEntriesOrRaws

Returns

Remarks

Example

Implementation of

Inherited from