BinaryTree

Class: BinaryTree<K, V, R>

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

A general Binary Tree implementation.

Remarks

This class implements a basic Binary Tree, not a Binary Search Tree. The set operation inserts nodes level-by-level (BFS) into the first available slot.

Examples

// determine loan approval using a decision tree
 // Decision tree structure
    const loanDecisionTree = new BinaryTree<string>(
      ['stableIncome', 'goodCredit', 'Rejected', 'Approved', 'Rejected'],
      { isDuplicate: true }
    );

    function determineLoanApproval(
      node?: BinaryTreeNode<string> | null,
      conditions?: { [key: string]: boolean }
    ): string {
      if (!node) throw new Error('Invalid node');

      // If it's a leaf node, return the decision result
      if (!node.left && !node.right) return node.key;

      // Check if a valid condition exists for the current node's key
      return conditions?.[node.key]
        ? determineLoanApproval(node.left, conditions)
        : determineLoanApproval(node.right, conditions);
    }

    // Test case 1: Stable income and good credit score
    console.log(determineLoanApproval(loanDecisionTree.root, { stableIncome: true, goodCredit: true })); // 'Approved';

    // Test case 2: Stable income but poor credit score
    console.log(determineLoanApproval(loanDecisionTree.root, { stableIncome: true, goodCredit: false })); // 'Rejected';

    // Test case 3: No stable income
    console.log(determineLoanApproval(loanDecisionTree.root, { stableIncome: false, goodCredit: true })); // 'Rejected';

    // Test case 4: No stable income and poor credit score
    console.log(determineLoanApproval(loanDecisionTree.root, { stableIncome: false, goodCredit: false })); // 'Rejected';

// evaluate the arithmetic expression represented by the binary tree
 const expressionTree = new BinaryTree<number | string>(['+', 3, '*', null, null, 5, '-', null, null, 2, 8]);

    function evaluate(node?: BinaryTreeNode<number | string> | null): number {
      if (!node) return 0;

      if (typeof node.key === 'number') return node.key;

      const leftValue = evaluate(node.left); // Evaluate the left subtree
      const rightValue = evaluate(node.right); // Evaluate the right subtree

      // Perform the operation based on the current node's operator
      switch (node.key) {
        case '+':
          return leftValue + rightValue;
        case '-':
          return leftValue - rightValue;
        case '*':
          return leftValue * rightValue;
        case '/':
          return rightValue !== 0 ? leftValue / rightValue : 0; // Handle division by zero
        default:
          throw new Error(`Unsupported operator: ${node.key}`);
      }
    }

    console.log(evaluate(expressionTree.root)); // -27;

Extends

IterableEntryBase<K, V | undefined>

Extended by

BST

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

Two Children Maximum: Each node has at most two children.
Left and Right Children: Nodes have distinct left and right children.
Depth and Height: Depth is the number of edges from the root to a node; height is the maximum depth in the tree.
Subtrees: Each child of a node forms the root of a subtree.
Leaf Nodes: Nodes without children are leaves.

Implements

IBinaryTree<K, V, R>

Constructors

Constructor

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

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

Creates an instance of BinaryTree.

Parameters

keysNodesEntriesOrRaws?

An iterable of items to set.

options?

BinaryTreeOptions<K, V, R>

Configuration options for the tree.

Returns

BinaryTree<K, V, R>

Remarks

Time O(N * M), where N is the number of items in keysNodesEntriesOrRaws and M is the tree size at insertion time (due to O(M) set operation). Space O(N) for storing the nodes.

Overrides

IterableEntryBase<K, V | undefined>.constructor

Properties

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

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

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

root

Get Signature

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

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

Gets the root node of the tree.

Remarks

Time O(1)

Returns

BinaryTreeNode<K, V> | null | undefined

The root node.

Implementation of

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

Overrides

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

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

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

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

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

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 (e.g., a full last level).

Template

The type of the callback function.

Param

Function to call on each node.

Param

The node to start from.

Param

The traversal method ('RECURSIVE' BFS is less common but supported here).

Param

If true, includes null nodes in the traversal.

Call Signature

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

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

BinaryTree level-order traversal

Returns

(K | undefined)[]

Example

// BinaryTree level-order traversal
 const tree = new BinaryTree([
      [1, 'one'],
      [2, 'two'],
      [3, 'three'],
      [4, 'four'],
      [5, 'five'],
      [6, 'six'],
      [7, 'seven']
    ]);

    // Binary tree maintains level-order insertion
    // Complete binary tree structure
    console.log(tree.size); // 7;

    // Verify all keys are present
    console.log(tree.has(1)); // true;
    console.log(tree.has(4)); // true;
    console.log(tree.has(7)); // true;

    // Iterate through tree
    const keys: number[] = [];
    for (const [key] of tree) {
      keys.push(key);
    }
    console.log(keys.length); // 7;

Implementation of

IBinaryTree.bfs

Call Signature

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

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

BinaryTree level-order traversal

Type Parameters

C

C extends NodeCallback<BinaryTreeNode<K, V>>

Parameters

callback?

C

startNode?

iterationType?

IterationType

includeNull?

false

Returns

ReturnType<C>[]

Example

// BinaryTree level-order traversal
 const tree = new BinaryTree([
      [1, 'one'],
      [2, 'two'],
      [3, 'three'],
      [4, 'four'],
      [5, 'five'],
      [6, 'six'],
      [7, 'seven']
    ]);

    // Binary tree maintains level-order insertion
    // Complete binary tree structure
    console.log(tree.size); // 7;

    // Verify all keys are present
    console.log(tree.has(1)); // true;
    console.log(tree.has(4)); // true;
    console.log(tree.has(7)); // true;

    // Iterate through tree
    const keys: number[] = [];
    for (const [key] of tree) {
      keys.push(key);
    }
    console.log(keys.length); // 7;

Implementation of

IBinaryTree.bfs

Call Signature

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

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

BinaryTree level-order traversal

Type Parameters

C

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

Parameters

callback?

C

startNode?

iterationType?

IterationType

includeNull?

true

Returns

ReturnType<C>[]

Example

// BinaryTree level-order traversal
 const tree = new BinaryTree([
      [1, 'one'],
      [2, 'two'],
      [3, 'three'],
      [4, 'four'],
      [5, 'five'],
      [6, 'six'],
      [7, 'seven']
    ]);

    // Binary tree maintains level-order insertion
    // Complete binary tree structure
    console.log(tree.size); // 7;

    // Verify all keys are present
    console.log(tree.has(1)); // true;
    console.log(tree.has(4)); // true;
    console.log(tree.has(7)); // true;

    // Iterate through tree
    const keys: number[] = [];
    for (const [key] of tree) {
      keys.push(key);
    }
    console.log(keys.length); // 7;

Implementation of

IBinaryTree.bfs

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

Overrides

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

Overrides

IterableEntryBase.clone

createNode()

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

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

(Protected) Creates a new node.

Parameters

key

K

The key for the new node.

value?

V

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

Returns

BinaryTreeNode<K, V>

The newly created node.

Remarks

Time O(1), Space O(1)

Implementation of

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

delete()

delete(keyNodeEntryRawOrPredicate): boolean;

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

Deletes a node from the tree.

Parameters

keyNodeEntryRawOrPredicate

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

The node to delete.

Returns

boolean

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

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

Example

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

Implementation of

IBinaryTree.delete

dfs()

Performs a Depth-First Search (DFS) traversal.

Remarks

Time O(N), visits every node. Space O(H) 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.

Param

If true, includes null nodes in the traversal.

Call Signature

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

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

Depth-first search traversal

Returns

(K | undefined)[]

Example

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

Implementation of

IBinaryTree.dfs

Call Signature

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

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

Depth-first search traversal

Type Parameters

C

C extends NodeCallback<BinaryTreeNode<K, V>>

Parameters

callback?

C

pattern?

DFSOrderPattern

onlyOne?

boolean

startNode?

iterationType?

IterationType

Returns

ReturnType<C>[]

Example

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

Implementation of

IBinaryTree.dfs

Call Signature

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

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

Depth-first search traversal

Type Parameters

C

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

Parameters

callback?

C

pattern?

DFSOrderPattern

onlyOne?

boolean

startNode?

iterationType?

IterationType

includeNull?

boolean

Returns

ReturnType<C>[]

Example

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

Implementation of

IBinaryTree.dfs

ensureNode()

ensureNode(keyNodeOrEntry, iterationType?): BinaryTreeNode<K, V> | null | undefined;

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

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

BinaryTreeNode<K, V> | null | undefined

The resolved node, or null/undefined if not found or input is null/undefined.

Remarks

Time O(1) if a node is passed. O(N) if a key or entry is passed (due to getNode performing a full search). Space O(1) if iterative search, O(H) if recursive (where H is height, O(N) worst-case).

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

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

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

Overrides

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

IterableEntryBase.find

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

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

Overrides

IterableEntryBase.get

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

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

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

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

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

getNode()

getNode(
   keyNodeEntryOrPredicate, 
   startNode?, 
   iterationType?): BinaryTreeNode<K, V> | null | undefined;

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

Gets the first node matching a predicate.

Parameters

keyNodeEntryOrPredicate

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

startNode?

The node to start the search from.

iterationType?

IterationType = ...

The traversal method.

Returns

BinaryTreeNode<K, V> | null | undefined

The first matching node, or undefined if not found.

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

// Get node by key
 const tree = new BinaryTree<number, string>([
      [1, 'root'],
      [2, 'child']
    ]);
    console.log(tree.getNode(2)?.value); // 'child';

Implementation of

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

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

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

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

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

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

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

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

Overrides

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

IterableEntryBase.hasValue

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

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

Overrides

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

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

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)

isNode()

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

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

Checks if the given item is a BinaryTreeNode instance.

Parameters

keyNodeOrEntry

The item to check.

Returns

keyNodeOrEntry is BinaryTreeNode<K, V>

True if it's a node, false otherwise.

Remarks

Time O(1), Space O(1)

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

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)

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)

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)

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)

isValidKey()

isValidKey(key): key is K;

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

Checks if the given key is valid (comparable or null).

Parameters

key

unknown

The key to validate.

Returns

key is K

True if the key is valid, false otherwise.

Remarks

Time O(1), Space O(1)

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

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

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

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.

Param

If true, includes null nodes.

Call Signature

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

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

Level-order grouping

Returns

(K | undefined)[][]

Example

// Level-order grouping
 const tree = new BinaryTree<number>([1, 2, 3, 4, 5]);
    const levels = tree.listLevels(node => node.key);
    console.log(levels[0]); // [1];
    console.log(levels[1].sort()); // [2, 3];

Implementation of

IBinaryTree.listLevels

Call Signature

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

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

Level-order grouping

Type Parameters

C

C extends NodeCallback<BinaryTreeNode<K, V>>

Parameters

callback?

C

startNode?

iterationType?

IterationType

includeNull?

false

Returns

ReturnType<C>[][]

Example

// Level-order grouping
 const tree = new BinaryTree<number>([1, 2, 3, 4, 5]);
    const levels = tree.listLevels(node => node.key);
    console.log(levels[0]); // [1];
    console.log(levels[1].sort()); // [2, 3];

Implementation of

IBinaryTree.listLevels

Call Signature

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

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

Level-order grouping

Type Parameters

C

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

Parameters

callback?

C

startNode?

iterationType?

IterationType

includeNull?

true

Returns

ReturnType<C>[][]

Example

// Level-order grouping
 const tree = new BinaryTree<number>([1, 2, 3, 4, 5]);
    const levels = tree.listLevels(node => node.key);
    console.log(levels[0]); // [1];
    console.log(levels[1].sort()); // [2, 3];

Implementation of

IBinaryTree.listLevels

map()

map<MK, MV, MR>(
   cb, 
   options?, 
thisArg?): BinaryTree<MK, MV, MR>;

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

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

Type Parameters

MK

MK = K

New key type.

MV

MV = V

New value type.

MR

MR = any

New raw type.

Parameters

cb

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

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

options?

Partial<BinaryTreeOptions<MK, MV, MR>>

Options for the new tree.

thisArg?

unknown

this context for the callback.

Returns

BinaryTree<MK, MV, MR>

A new, mapped tree.

Remarks

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

Example

// Transform to new tree
 const tree = new BinaryTree<number, number>([
      [1, 10],
      [2, 20]
    ]);
    const mapped = tree.map((v, key) => [key, (v ?? 0) + 1] as [number, number]);
    console.log([...mapped.values()]); // contains 11;

Implementation of

IBinaryTree.map

Overrides

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

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

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

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

Overrides

IterableEntryBase.print

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

IterableEntryBase.reduce

search()

Searches the tree for nodes matching a predicate.

Remarks

Time O(N) — full DFS scan; may visit every node. Space O(H) for call/explicit stack (O(N) worst-case). BST subclasses with key search override to O(log N).

Template

The type of the callback function.

Param

The key, node, entry, or predicate function 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/binary-tree.ts:808

Search by predicate

Parameters

keyNodeEntryOrPredicate

onlyOne?

boolean

Returns

(K | undefined)[]

Example

// Search by predicate
 const tree = new BinaryTree<number>([5, 3, 7, 1, 9]);
    const found = tree.search(n => n!.key > 5, true);
    console.log(found.length); // >= 1;

Implementation of

IBinaryTree.search

Call Signature

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

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

Search by predicate

Type Parameters

C

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

Parameters

keyNodeEntryOrPredicate

onlyOne

boolean

callback

C

startNode?

iterationType?

IterationType

Returns

ReturnType<C>[]

Example

// Search by predicate
 const tree = new BinaryTree<number>([5, 3, 7, 1, 9]);
    const found = tree.search(n => n!.key > 5, true);
    console.log(found.length); // >= 1;

Implementation of

IBinaryTree.search

set()

set(keyNodeOrEntry, value?): boolean;

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

Adds or updates a new node to the tree.

Parameters

keyNodeOrEntry

The key, node, or entry to set or update.

value?

V

The value, if providing just a key.

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

// basic BinaryTree creation and insertion
 // Create a BinaryTree with entries
    const entries: [number, string][] = [
      [6, 'six'],
      [1, 'one'],
      [2, 'two'],
      [7, 'seven'],
      [5, 'five'],
      [3, 'three'],
      [4, 'four'],
      [9, 'nine'],
      [8, 'eight']
    ];

    const tree = new BinaryTree(entries);

    // Verify size
    console.log(tree.size); // 9;

    // Add new element
    tree.set(10, 'ten');
    console.log(tree.size); // 10;

Implementation of

IBinaryTree.set

setMany()

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

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

Adds or updates multiple items to the tree.

Parameters

keysNodesEntriesOrRaws

An iterable of items to set or update.

values?

Iterable<V | undefined, any, any>

An optional parallel iterable of values.

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

// Set multiple entries
 const tree = new BinaryTree<number, string>();
    tree.setMany([
      [1, 'a'],
      [2, 'b'],
      [3, 'c']
    ]);
    console.log(tree.size); // 3;

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

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

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

Overrides

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

IterableEntryBase.values

Protected Members

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

Accessors

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

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

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

_createInstance()

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

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

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

Type Parameters

TK

TK = K

TV

TV = V

TR

TR = R

Parameters

options?

Partial<BinaryTreeOptions<TK, TV, TR>>

Options for the new tree.

Returns

this

A new, empty tree.

Remarks

Time O(1)

_createLike()

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

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

(Protected) Creates a new instance of the same tree 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<BinaryTreeOptions<TK, TV, TR>>

Options for the new tree.

Returns

BinaryTree<TK, TV, TR>

A new tree.

Remarks

Time O(N) (or as per constructor) due to processing the iterable.

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

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

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

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

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

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

Overrides

IterableEntryBase._getIterator

_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

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

_keyValueNodeOrEntryToNodeAndValue()

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

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

(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

[BinaryTreeNode<K, V> | null | undefined, V | undefined]

A tuple of [node, value].

Remarks

Time O(1)

_replaceNode()

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

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

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

Parameters

oldNode

BinaryTreeNode<K, V>

The node to be replaced.

newNode

BinaryTreeNode<K, V>

The node to insert.

Returns

BinaryTreeNode<K, V>

The newNode.

Remarks

Time O(1)

_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

_setRoot()

protected _setRoot(v): void;

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

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

Parameters

v

BinaryTreeNode<K, V> | null | undefined

The node to set as root.

Returns

void

Remarks

Time O(1)

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

_snapshotOptions()

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

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

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

Type Parameters

TK

TK = K

TV

TV = V

TR

TR = R

Returns

BinaryTreeOptions<TK, TV, TR>

The options object.

Remarks

Time O(1)

_swapProperties()

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

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

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

Class: BinaryTree<K, V, R>

Remarks​

Examples​

Extends​

Extended by​

Type Parameters​

K​

V​

R​

Implements​

Constructors​

Constructor​

Parameters​

keysNodesEntriesOrRaws?​

options?​

Returns​

Remarks​

Overrides​

Properties​

isDuplicate​

Get Signature​

Remarks​

Returns​

Implementation of​

isMapMode​

Get Signature​

Remarks​

Returns​

Implementation of​

NIL​

Get Signature​

Remarks​

Returns​

Implementation of​

root​

Get Signature​

Remarks​

Returns​

Implementation of​

size​

Get Signature​

Remarks​

Returns​

Implementation of​

Overrides​

store​

Get Signature​

Remarks​

Returns​

Implementation of​

toEntryFn​

Get Signature​

Remarks​

Returns​

Implementation of​

Methods​

[iterator]()​

Parameters​

args​

Returns​

Remarks​

Implementation of​

Inherited from​

add()​

Parameters​

keyNodeOrEntry​

Returns​

Remarks​

Example​

Implementation of​

addMany()​

Parameters​

keysNodesEntriesOrRaws​

Returns​

Remarks​

Example​

Implementation of​

bfs()​

Remarks​

Template​

Remarks

Examples

Extends

Extended by

Type Parameters

K

V

R

Implements

Constructors

Constructor

Parameters

keysNodesEntriesOrRaws?

options?

Returns

Remarks

Overrides

Properties

isDuplicate

Get Signature

Remarks

Returns

Implementation of

isMapMode

Get Signature

Remarks

Returns

Implementation of

NIL

Get Signature

Remarks

Returns

Implementation of

root

Get Signature

Remarks

Returns

Implementation of

size

Get Signature

Remarks

Returns

Implementation of

Overrides

store

Get Signature

Remarks

Returns

Implementation of

toEntryFn

Get Signature

Remarks

Returns

Implementation of

Methods

[iterator]()

Parameters

args

Returns

Remarks

Implementation of

Inherited from

add()

Parameters

keyNodeOrEntry

Returns

Remarks

Example

Implementation of

addMany()

Parameters

keysNodesEntriesOrRaws

Returns

Remarks

Example

Implementation of

bfs()

Remarks

Template

Param