AVLTree

Class: AVLTree<K, V, R>

Defined in: data-structures/binary-tree/avl-tree.ts:309

Represents a self-balancing AVL (Adelson-Velsky and Landis) Tree. This tree extends BST and performs rotations on set/delete to maintain balance.

Examples

// AVLTree has and get operations
 const tree = new AVLTree<number>([11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5]);

    // Check if element exists
    console.log(tree.has(6)); // true;
    console.log(tree.has(99)); // false;

    // Get node by key
    const node = tree.getNode(6);
    console.log(node?.key); // 6;

    // Verify tree is balanced
    console.log(tree.isAVLBalanced()); // true;

// AVLTree for university ranking system with strict balance
 interface University {
      name: string;
      rank: number;
      students: number;
    }

    // AVLTree provides highest search efficiency with strict balance
    // (every node's left/right subtrees differ by at most 1 in height)
    const universityTree = new AVLTree<number, University>([
      [1, { name: 'MIT', rank: 1, students: 1200 }],
      [5, { name: 'Stanford', rank: 5, students: 1800 }],
      [3, { name: 'Harvard', rank: 3, students: 2300 }],
      [2, { name: 'Caltech', rank: 2, students: 400 }],
      [4, { name: 'CMU', rank: 4, students: 1500 }]
    ]);

    // Quick lookup by rank
    const mit = universityTree.get(1);
    console.log(mit?.name); // 'MIT';

    const cmulevel = universityTree.getHeight(4);
    console.log(typeof cmulevel); // 'number';

    // Tree maintains strict balance during insertions and deletions
    console.log(universityTree.isAVLBalanced()); // true;

    // Add more universities
    universityTree.set(6, { name: 'Oxford', rank: 6, students: 2000 });
    console.log(universityTree.isAVLBalanced()); // true;

    // Delete and verify balance is maintained
    universityTree.delete(2);
    console.log(universityTree.has(2)); // false;
    console.log(universityTree.isAVLBalanced()); // true;

    // Get all remaining universities in rank order
    const remainingRanks = [...universityTree.keys()];
    console.log(remainingRanks); // [1, 3, 4, 5, 6];
    console.log(universityTree.size); // 5;

// Find elements in a range
 // In interval queries, AVL trees, with their strictly balanced structure and lower height, offer better query efficiency, making them ideal for frequent and high-performance interval queries. In contrast, Red-Black trees, with lower update costs, are more suitable for scenarios involving frequent insertions and deletions where the requirements for interval queries are less demanding.
    type Datum = { timestamp: Date; temperature: number };
    // Fixed dataset of CPU temperature readings
    const cpuData: Datum[] = [
      { timestamp: new Date('2024-12-02T00:00:00'), temperature: 55.1 },
      { timestamp: new Date('2024-12-02T00:01:00'), temperature: 56.3 },
      { timestamp: new Date('2024-12-02T00:02:00'), temperature: 54.8 },
      { timestamp: new Date('2024-12-02T00:03:00'), temperature: 57.2 },
      { timestamp: new Date('2024-12-02T00:04:00'), temperature: 58.0 },
      { timestamp: new Date('2024-12-02T00:05:00'), temperature: 59.4 },
      { timestamp: new Date('2024-12-02T00:06:00'), temperature: 60.1 },
      { timestamp: new Date('2024-12-02T00:07:00'), temperature: 61.3 },
      { timestamp: new Date('2024-12-02T00:08:00'), temperature: 62.0 },
      { timestamp: new Date('2024-12-02T00:09:00'), temperature: 63.5 },
      { timestamp: new Date('2024-12-02T00:10:00'), temperature: 64.0 },
      { timestamp: new Date('2024-12-02T00:11:00'), temperature: 62.8 },
      { timestamp: new Date('2024-12-02T00:12:00'), temperature: 61.5 },
      { timestamp: new Date('2024-12-02T00:13:00'), temperature: 60.2 },
      { timestamp: new Date('2024-12-02T00:14:00'), temperature: 59.8 },
      { timestamp: new Date('2024-12-02T00:15:00'), temperature: 58.6 },
      { timestamp: new Date('2024-12-02T00:16:00'), temperature: 57.4 },
      { timestamp: new Date('2024-12-02T00:17:00'), temperature: 56.2 },
      { timestamp: new Date('2024-12-02T00:18:00'), temperature: 55.7 },
      { timestamp: new Date('2024-12-02T00:19:00'), temperature: 54.5 },
      { timestamp: new Date('2024-12-02T00:20:00'), temperature: 53.2 },
      { timestamp: new Date('2024-12-02T00:21:00'), temperature: 52.8 },
      { timestamp: new Date('2024-12-02T00:22:00'), temperature: 51.9 },
      { timestamp: new Date('2024-12-02T00:23:00'), temperature: 50.5 },
      { timestamp: new Date('2024-12-02T00:24:00'), temperature: 49.8 },
      { timestamp: new Date('2024-12-02T00:25:00'), temperature: 48.7 },
      { timestamp: new Date('2024-12-02T00:26:00'), temperature: 47.5 },
      { timestamp: new Date('2024-12-02T00:27:00'), temperature: 46.3 },
      { timestamp: new Date('2024-12-02T00:28:00'), temperature: 45.9 },
      { timestamp: new Date('2024-12-02T00:29:00'), temperature: 45.0 }
    ];

    // Create an AVL tree to store CPU temperature data
    const cpuTemperatureTree = new AVLTree<Date, number, Datum>(cpuData, {
      toEntryFn: ({ timestamp, temperature }) => [timestamp, temperature]
    });

    // Query a specific time range (e.g., from 00:05 to 00:15)
    const rangeStart = new Date('2024-12-02T00:05:00');
    const rangeEnd = new Date('2024-12-02T00:15:00');
    const rangeResults = cpuTemperatureTree.rangeSearch([rangeStart, rangeEnd], node => ({
      minute: node ? node.key.getMinutes() : 0,
      temperature: cpuTemperatureTree.get(node ? node.key : undefined)
    }));

    console.log(rangeResults); // [
 //      { minute: 5, temperature: 59.4 },
 //      { minute: 6, temperature: 60.1 },
 //      { minute: 7, temperature: 61.3 },
 //      { minute: 8, temperature: 62 },
 //      { minute: 9, temperature: 63.5 },
 //      { minute: 10, temperature: 64 },
 //      { minute: 11, temperature: 62.8 },
 //      { minute: 12, temperature: 61.5 },
 //      { minute: 13, temperature: 60.2 },
 //      { minute: 14, temperature: 59.8 },
 //      { minute: 15, temperature: 58.6 }
 //    ];

Extends

BST<K, V, R>

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

Height-Balanced: Each node's left and right subtrees differ in height by no more than one.
Automatic Rebalancing: AVL trees rebalance themselves automatically during insertions and deletions.
Rotations for Balancing: Utilizes rotations (single or double) to maintain balance after updates.
Order Preservation: Maintains the binary search tree property where left child values are less than the parent, and right child values are greater.
Efficient Lookups: Offers O(log n) search time, where 'n' is the number of nodes, due to its balanced nature.
Complex Insertions and Deletions: Due to rebalancing, these operations are more complex than in a regular BST.
Path Length: The path length from the root to any leaf is longer compared to an unbalanced BST, but shorter than a linear chain of nodes.

Implements

IBinaryTree<K, V, R>

Constructors

Constructor

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

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

Creates an instance of AVLTree.

Parameters

keysNodesEntriesOrRaws?

An iterable of items to set.

options?

AVLTreeOptions<K, V, R>

Configuration options for the AVL tree.

Returns

AVLTree<K, V, R>

Remarks

Time O(N log N) (from setMany with balanced set). Space O(N).

Overrides

BST.constructor

Properties

comparator

Get Signature

get comparator(): Comparator<K>;

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

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:326

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:316

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(): OptNode<BSTNode<K, V>>;

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

Gets the root node of the tree.

Remarks

Time O(1)

Returns

OptNode<BSTNode<K, V>>

The root node.

Implementation of

IBinaryTree.root

Inherited from

BST.root

size

Get Signature

get size(): number;

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

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:339

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:383

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:609

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(N) — level-order traversal to find an empty slot. Space O(N) for the BFS queue. BST/Red-Black Tree/AVL Tree subclasses override to O(log N).

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:711

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:493

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:494

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:1253

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:1268

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/binary-tree.ts:1087

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

BST.clear

clone()

clone(): this;

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

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?): AVLTreeNode<K, V>;

Defined in: data-structures/binary-tree/avl-tree.ts:336

(Protected) Creates a new AVL tree node.

Parameters

key

K

The key for the new node.

value?

V

The value for the new node.

Returns

AVLTreeNode<K, V>

The newly created AVLTreeNode.

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:439

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(keyNodeOrEntry): boolean;

Defined in: data-structures/binary-tree/avl-tree.ts:391

Deletes a node from the AVL tree and re-balances the tree.

Parameters

keyNodeOrEntry

The node to delete.

Returns

boolean

An array containing deletion results.

Remarks

Time O(log N) (O(H) for BST delete + O(H) for _balancePath). Space O(H) for path/recursion.

Example

// Remove nodes and verify structure
 const avl = new AVLTree<number>([5, 3, 7, 1, 4, 6, 8]);
    avl.delete(3);
    console.log(avl.has(3)); // false;
    console.log(avl.size); // 6;

Implementation of

IBinaryTree.delete

Overrides

BST.delete

deleteWhere()

deleteWhere(
   keyNodeEntryOrPredicate, 
   onlyOne?, 
   startNode?, 
   iterationType?): boolean;

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

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

boolean

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:453

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:455

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:414

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:1958

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:1394

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:1409

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:995

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(1) in Map mode, O(N) otherwise (via getNode). Space O(1) in Map mode, O(H) or O(N) otherwise. BST subclasses override non-Map-mode to O(log N).

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

getByRank()

Call Signature

getByRank(k): K | undefined;

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

Returns the element at the k-th position in tree order (0-indexed).

Parameters

k

number

The 0-based position in tree order (0 = first element).

Returns

K | undefined

The key at position k, or undefined if out of bounds.

Remarks

Time O(log n), Space O(1) iterative / O(log n) recursive. Requires enableOrderStatistic: true. Tree order is defined by the comparator — ascending by default, but respects custom comparators (e.g. descending).

Example

// Order-statistic on BST
 const tree = new BST<number>([30, 10, 50, 20, 40], { enableOrderStatistic: true });
      console.log(tree.getByRank(0)); // 10;
      console.log(tree.getByRank(4)); // 50;
      console.log(tree.getRank(30)); // 2;

Inherited from

BST.getByRank

Call Signature

getByRank<C>(
   k, 
   callback, 
   iterationType?): ReturnType<C> | undefined;

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

Returns the element at the k-th position in tree order and applies a callback.

Type Parameters

C

C extends NodeCallback<BSTNode<K, V>>

Parameters

k

number

The 0-based position in tree order (0 = first element).

callback

C

Callback to apply to the found node.

iterationType?

IterationType

Iteration strategy ('ITERATIVE' or 'RECURSIVE').

Returns

ReturnType<C> | undefined

The callback result, or undefined if out of bounds.

Remarks

Time O(log n), Space O(1) iterative / O(log n) recursive. Requires enableOrderStatistic: true.

Inherited from

BST.getByRank

getDepth()

getDepth(dist, startNode?): number;

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

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:1216

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:1343

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:1345

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:1258

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:574

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:912

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:1305

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:1309

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:1443

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

getRank()

Call Signature

getRank(keyNodeEntryOrPredicate): number;

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

Returns the 0-based rank of a key (number of elements that precede it in tree order).

Parameters

keyNodeEntryOrPredicate

The key, node, entry [K, V], or predicate to find.

Returns

number

The rank (0-indexed), or -1 if the tree is empty or input is invalid.

Remarks

Time O(log n), Space O(1) iterative / O(log n) recursive. Requires enableOrderStatistic: true. Tree order is defined by the comparator. When the key is not found, returns the insertion position.

Inherited from

BST.getRank

Call Signature

getRank(keyNodeEntryOrPredicate, iterationType): number;

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

Returns the 0-based rank (number of preceding elements in tree order) with explicit iteration type.

Parameters

keyNodeEntryOrPredicate

The key, node, entry, or predicate to find.

iterationType

IterationType

Iteration strategy ('ITERATIVE' or 'RECURSIVE').

Returns

number

The rank (0-indexed), or -1 if the tree is empty or input is invalid.

Remarks

Time O(log n), Space O(1) iterative / O(log n) recursive. Requires enableOrderStatistic: true.

Inherited from

BST.getRank

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:1390

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:1392

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:1464

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:1045

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(N) via search. Space O(H) or O(N). BST/Red-Black Tree/AVL Tree subclasses override to O(log N) for key lookups.

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:1323

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:1338

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:1722

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:1131

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:1101

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:576

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:562

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:531

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 AVLTreeNode<K, V>;

Defined in: data-structures/binary-tree/avl-tree.ts:347

Checks if the given item is an AVLTreeNode instance.

Parameters

keyNodeOrEntry

The item to check.

Returns

keyNodeOrEntry is AVLTreeNode<K, V>

True if it's an AVLTreeNode, false otherwise.

Remarks

Time O(1), Space O(1)

Overrides

BST.isNode

isPerfectlyBalanced()

isPerfectlyBalanced(startNode?): boolean;

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

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:542

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:491

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:504

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:518

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:441

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:1655

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:1657

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:1614

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:1616

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:529

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); // toBeInstanceOf;
    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:531

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); // toBeInstanceOf;
    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:1509

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:1524

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?): AVLTree<MK, MV, MR>;

Defined in: data-structures/binary-tree/avl-tree.ts:466

Creates a new AVLTree by mapping each [key, value] pair.

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<BinaryTreeOptions<MK, MV, MR>>

Options for the new AVLTree.

thisArg?

unknown

this context for the callback.

Returns

AVLTree<MK, MV, MR>

A new, mapped AVLTree.

Remarks

Time O(N log N) (O(N) iteration + O(log M) set for each item into the new tree). Space O(N) for the new tree.

Example

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

Implementation of

IBinaryTree.map

Overrides

BST.map

merge()

merge(anotherTree): void;

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

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:1809

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:1811

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/avl-tree.ts:420

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

AVL trees are already height-balanced, but this makes them perfectly balanced (minimal height and all leaves at N or N-1). 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 avl = new AVLTree<number>();
    // Insert in sorted order (worst case for BST)
    for (let i = 1; i <= 7; i++) avl.add(i);
    console.log(avl.isAVLBalanced()); // false;
    avl.perfectlyBalance();
    console.log(avl.isAVLBalanced()); // true;

Overrides

BST.perfectlyBalance

print()

print(options?, startNode?): void;

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

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

rangeByRank()

Call Signature

rangeByRank(start, end): (K | undefined)[];

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

Returns elements by position range in tree order (0-indexed, inclusive on both ends).

Parameters

start

number

Start position (inclusive, 0-indexed). Clamped to 0 if negative.

end

number

End position (inclusive, 0-indexed). Clamped to size-1 if too large.

Returns

(K | undefined)[]

Array of keys in tree order within the specified range.

Remarks

Time O(log n + k), Space O(k), where k = end - start + 1. Requires enableOrderStatistic: true.

Inherited from

BST.rangeByRank

Call Signature

rangeByRank<C>(
   start, 
   end, 
   callback, 
   iterationType?): ReturnType<C>[];

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

Returns elements by position range in tree order with callback and optional iteration type.

Type Parameters

C

C extends NodeCallback<BSTNode<K, V>>

Parameters

start

number

Start rank (inclusive, 0-indexed).

end

number

End rank (inclusive, 0-indexed).

callback

C

Callback to apply to each node in the range.

iterationType?

IterationType

Iteration strategy ('ITERATIVE' or 'RECURSIVE').

Returns

ReturnType<C>[]

Array of callback results for nodes in the rank range.

Remarks

Time O(log n + k), Space O(k), where k = end - start + 1. Requires enableOrderStatistic: true.

Inherited from

BST.rangeByRank

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:807

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:809

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

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:646

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:658

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/avl-tree.ts:367

Sets a new node to the AVL tree and balances the tree path.

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) (O(H) for BST set + O(H) for _balancePath). Space O(H) for path/recursion.

Example

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

Implementation of

IBinaryTree.set

Overrides

BST.set

setMany()

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

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

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

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:2004

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:340

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:2298

(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

Accessors

_balanceFactor()

protected _balanceFactor(node): number;

Defined in: data-structures/binary-tree/avl-tree.ts:558

(Protected) Calculates the balance factor (height(right) - height(left)).

Parameters

node

AVLTreeNode<K, V>

The node to check.

Returns

number

The balance factor (positive if right-heavy, negative if left-heavy).

Remarks

Time O(1) (assumes heights are stored).

_balanceLL()

protected _balanceLL(A): void;

Defined in: data-structures/binary-tree/avl-tree.ts:582

(Protected) Performs a Left-Left (LL) rotation (a single right rotation).

Parameters

A

AVLTreeNode<K, V>

The unbalanced node (root of the unbalanced subtree).

Returns

void

Remarks

Time O(1), Space O(1)

_balanceLR()

protected _balanceLR(A): void;

Defined in: data-structures/binary-tree/avl-tree.ts:617

(Protected) Performs a Left-Right (LR) double rotation.

Parameters

A

AVLTreeNode<K, V>

The unbalanced node (root of the unbalanced subtree).

Returns

void

Remarks

Time O(1), Space O(1)

_balancePath()

protected _balancePath(node): void;

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

(Protected) Traverses up the tree from the specified node, updating heights and performing rotations as needed.

Parameters

node

The node to start balancing from (e.g., the newly inserted node or parent of the deleted node).

Returns

void

Remarks

Time O(log N) (O(H)), as it traverses the path to root. Space O(H) for the path array.

_balanceRL()

protected _balanceRL(A): void;

Defined in: data-structures/binary-tree/avl-tree.ts:707

(Protected) Performs a Right-Left (RL) double rotation.

Parameters

A

AVLTreeNode<K, V>

The unbalanced node (root of the unbalanced subtree).

Returns

void

Remarks

Time O(1), Space O(1)

_balanceRR()

protected _balanceRR(A): void;

Defined in: data-structures/binary-tree/avl-tree.ts:668

(Protected) Performs a Right-Right (RR) rotation (a single left rotation).

Parameters

A

AVLTreeNode<K, V>

The unbalanced node (root of the unbalanced subtree).

Returns

void

Remarks

Time O(1), Space O(1)

_bound()

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

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

(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:2196

(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:2251

(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:2701

(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:2710

(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:2392

(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:2517

(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:1866

(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/avl-tree.ts:489

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

Type Parameters

TK

TK = K

TV

TV = V

TR

TR = R

Parameters

options?

Partial<AVLTreeOptions<TK, TV, TR>>

Options for the new tree.

Returns

this

A new, empty tree.

Remarks

Time O(1)

Overrides

BST._createInstance

_createLike()

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

Defined in: data-structures/binary-tree/avl-tree.ts:506

(Protected) Creates a new instance of the same AVLTree 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 tree.

options?

Partial<AVLTreeOptions<TK, TV, TR>>

Options for the new tree.

Returns

AVLTree<TK, TV, TR>

A new AVLTree.

Remarks

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

Overrides

BST._createLike

_deleteByKey()

protected _deleteByKey(key): boolean;

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

(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

_deleteInternal()

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

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

Internal

Deletes a node from the tree (internal, returns balancing metadata).

Parameters

keyNodeEntryRawOrPredicate

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

The node to delete.

Returns

BinaryTreeDeleteResult<BinaryTreeNode<K, V>>[]

An array containing deletion results with balancing metadata.

Remarks

Time O(N) — O(N) to find the node + O(H) for predecessor swap. Space O(1). BST/Red-Black Tree/AVL Tree subclasses override to O(log N). Used by AVL/BST subclasses that need balancing metadata after deletion.

Inherited from

BST._deleteInternal

_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:2109

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:2416

(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:2607

(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:2667

(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

_floorByKey()

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

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

(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:1957

(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

_getByRankIterative()

protected _getByRankIterative(node, k): BSTNode<K, V> | undefined;

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

(Protected) Finds the node at position k in tree order (iterative).

Parameters

node

OptNode<BSTNode<K, V>>

k

number

Returns

BSTNode<K, V> | undefined

Remarks

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

Inherited from

BST._getByRankIterative

_getByRankRecursive()

protected _getByRankRecursive(node, k): BSTNode<K, V> | undefined;

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

(Protected) Finds the node at position k in tree order (recursive).

Parameters

node

OptNode<BSTNode<K, V>>

k

number

Returns

BSTNode<K, V> | undefined

Remarks

Time O(log n), Space O(log n) call stack

Inherited from

BST._getByRankRecursive

_getIterator()

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

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

(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

_getRankIterative()

protected _getRankIterative(node, key): number;

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

(Protected) Computes the rank of a key iteratively.

Parameters

node

OptNode<BSTNode<K, V>>

key

K

Returns

number

Remarks

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

Inherited from

BST._getRankIterative

_getRankRecursive()

protected _getRankRecursive(node, key): number;

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

(Protected) Computes the rank of a key recursively.

Parameters

node

OptNode<BSTNode<K, V>>

key

K

Returns

number

Remarks

Time O(log n), Space O(log n) call stack

Inherited from

BST._getRankRecursive

_isDisplayLeaf()

protected _isDisplayLeaf(node, options): boolean;

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

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:2656

(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:2364

(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

_lowerByKey()

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

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

(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:2075

(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

_next()

protected _next(node): BSTNode<K, V> | undefined;

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

(Protected) Finds the in-order successor of a node.

Parameters

node

BSTNode<K, V>

Returns

BSTNode<K, V> | undefined

Remarks

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

Inherited from

BST._next

_replaceNode()

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

Defined in: data-structures/binary-tree/avl-tree.ts:802

(Protected) Replaces a node, ensuring height is copied.

Parameters

oldNode

AVLTreeNode<K, V>

The node to be replaced.

newNode

AVLTreeNode<K, V>

The node to insert.

Returns

AVLTreeNode<K, V>

The newNode.

Remarks

Time O(1)

Overrides

BST._replaceNode

_resolveDisplayLeaf()

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

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

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

_setRoot()

protected _setRoot(v): void;

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

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

Inherited from

BST._setRoot

_setValue()

protected _setValue(key, value): boolean;

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

(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:2348

(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

_swapProperties()

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

Defined in: data-structures/binary-tree/avl-tree.ts:525

(Protected) Swaps properties of two nodes, including height.

Parameters

srcNode

BSTNOptKeyOrNode<K, AVLTreeNode<K, V>>

The source node.

destNode

BSTNOptKeyOrNode<K, AVLTreeNode<K, V>>

The destination node.

Returns

AVLTreeNode<K, V> | undefined

The destNode (now holding srcNode's properties).

Remarks

Time O(H) (due to ensureNode), but O(1) if nodes are passed directly.

Overrides

BST._swapProperties

_updateCount()

protected _updateCount(node): void;

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

(Protected) Recalculates the subtree count for a single node.

Parameters

node

BSTNode<K, V>

Returns

void

Remarks

Time O(1). Only active when enableOrderStatistic is true.

Inherited from

BST._updateCount

_updateCountAlongPath()

protected _updateCountAlongPath(node): void;

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

(Protected) Updates subtree counts from a node up to the root.

Parameters

node

OptNode<BSTNode<K, V>>

Returns

void

Remarks

Time O(log n). Only active when enableOrderStatistic is true.

Inherited from

BST._updateCountAlongPath

_updateHeight()

protected _updateHeight(node): void;

Defined in: data-structures/binary-tree/avl-tree.ts:570

(Protected) Recalculates and updates the height of a node based on its children's heights.

Parameters

node

AVLTreeNode<K, V>

The node to update.

Returns

void

Remarks

Time O(1) (assumes children's heights are correct).

Class: AVLTree<K, V, R>

Examples​

Extends​

Type Parameters​

K​

V​

R​

Implements​

Constructors​

Constructor​

Parameters​

keysNodesEntriesOrRaws?​

options?​

Returns​

Remarks​

Overrides​

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​

Inherited from​

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

Type Parameters

K

V

R

Implements

Constructors

Constructor

Parameters

keysNodesEntriesOrRaws?

options?

Returns

Remarks

Overrides

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

Inherited from

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