Class AVLTreeCounter<K, V, R>

AVL tree that tracks an aggregate 'count' across nodes; supports balanced insert/delete and map-like mode.

Remarks

Time O(1), Space O(1)

Type Parameters

K = any
V = any
R extends object = object

Hierarchy (view full)

AVLTree<K, V, R>
- AVLTreeCounter

Implements

IBinaryTree<K, V, R>

Index

Constructors

constructor

new AVLTreeCounter<K, V, R>(keysNodesEntriesOrRaws?, options?): AVLTreeCounter<K, V, R>
Create a AVLTreeCounter instance
Type Parameters
- K = any
- V = any
- R extends object = object
Parameters
- keysNodesEntriesOrRaws: Iterable<
      | undefined
      | null
      | K
      | R
      | AVLTreeCounterNode<K, V>
      | [undefined | null | K, undefined | V], any, any> = []
- Optionaloptions: AVLTreeCounterOptions<K, V, R>
Returns AVLTreeCounter<K, V, R>
New AVLTreeCounterNode instance.

Remarks
Time O(n), Space O(n)
Overrides AVLTree.constructor
- Defined in data-structures/binary-tree/avl-tree-counter.ts:109

Properties

`Protected`_comparator

_comparator: Comparator<K> = ...

The default comparator function.

Remarks

Time O(1) (or O(C) if specifyComparable is used, C is complexity of that function).

Accessors

comparator

get comparator(): Comparator<K>
Gets the comparator function used by the tree.

Returns Comparator<K>
The comparator function.

Remarks
Time O(1)
Inherited from AVLTree.comparator
- Defined in data-structures/binary-tree/bst.ts:250

isDuplicate

get isDuplicate(): boolean
Gets whether the tree allows duplicate keys.

Returns boolean
True if duplicates are allowed, false otherwise.

Remarks
Time O(1)
Implementation of IBinaryTree.isDuplicate
Inherited from AVLTree.isDuplicate
- Defined in data-structures/binary-tree/binary-tree.ts:321

isMapMode

get isMapMode(): boolean
Gets whether the tree is in Map mode.

Returns boolean
True if in Map mode, false otherwise.

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)
Implementation of IBinaryTree.isMapMode
Inherited from AVLTree.isMapMode
- Defined in data-structures/binary-tree/binary-tree.ts:309

isReverse

get isReverse(): boolean
Gets whether the tree's comparison logic is reversed.

Returns boolean
True if the tree is reversed (e.g., a max-heap logic).

Remarks
Time O(1)
Inherited from AVLTree.isReverse
- Defined in data-structures/binary-tree/bst.ts:215

NIL

get NIL(): BinaryTreeNode<K, V>
Gets the sentinel NIL node (used in self-balancing trees like Red-Black Tree).

Returns BinaryTreeNode<K, V>
The NIL node.

Remarks
Time O(1)
Implementation of IBinaryTree.NIL
Inherited from AVLTree.NIL
- Defined in data-structures/binary-tree/binary-tree.ts:369

root

get root(): OptNode<BSTNode<K, V>>
Gets the root node of the tree.

Returns OptNode<BSTNode<K, V>>
The root node.

Remarks
Time O(1)
Implementation of IBinaryTree.root
Inherited from AVLTree.root
- Defined in data-structures/binary-tree/bst.ts:203

size

get size(): number
Gets the number of nodes in the tree.

Returns number
The size of the tree.

Remarks
Time O(1)
Implementation of IBinaryTree.size
Inherited from AVLTree.size
- Defined in data-structures/binary-tree/binary-tree.ts:357

specifyComparable

get specifyComparable(): undefined | ((key: K) => Comparable)
Gets the function used to extract a comparable value from a complex key.

Returns undefined | ((key: K) => Comparable)
The key-to-comparable conversion function.

Remarks
Time O(1)
Inherited from AVLTree.specifyComparable
- Defined in data-structures/binary-tree/bst.ts:262

store

get store(): Map<K, undefined | V>
Gets the external value store (used in Map mode).

Returns Map<K, undefined | V>
The map storing key-value pairs.

Remarks
Time O(1)
Implementation of IBinaryTree.store
Inherited from AVLTree.store
- Defined in data-structures/binary-tree/binary-tree.ts:333

toEntryFn

get toEntryFn(): undefined | ToEntryFn<K, V, R>
Gets the function used to convert raw data objects (R) into [key, value] entries.

Returns undefined | ToEntryFn<K, V, R>
The conversion function.

Remarks
Time O(1)
Implementation of IBinaryTree.toEntryFn
Inherited from AVLTree.toEntryFn
- Defined in data-structures/binary-tree/binary-tree.ts:381

Methods

`Protected`_balanceFactor

_balanceFactor(node): number
(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).
Inherited from AVLTree._balanceFactor
- Defined in data-structures/binary-tree/avl-tree.ts:403

`Protected`_balanceLL

_balanceLL(A): void
(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)
Inherited from AVLTree._balanceLL
- Defined in data-structures/binary-tree/avl-tree.ts:427

`Protected`_balanceLR

_balanceLR(A): void
(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)
Inherited from AVLTree._balanceLR
- Defined in data-structures/binary-tree/avl-tree.ts:462

`Protected`_balancePath

_balancePath(node): void
(Protected) Traverses up the tree from the specified node, updating heights and performing rotations as needed.
Parameters
- node:
      | undefined
      | null
      | K
      | AVLTreeNode<K, V>
      | [undefined | null | K, undefined | V]
  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.
Inherited from AVLTree._balancePath
- Defined in data-structures/binary-tree/avl-tree.ts:604

`Protected`_balanceRL

_balanceRL(A): void
(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)
Inherited from AVLTree._balanceRL
- Defined in data-structures/binary-tree/avl-tree.ts:553

`Protected`_balanceRR

_balanceRR(A): void
(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)
Inherited from AVLTree._balanceRR
- Defined in data-structures/binary-tree/avl-tree.ts:514

`Protected`_clearNodes

_clearNodes(): void
(Protected) Clears all nodes from the tree.

Returns void
Remarks
Time O(1)
Inherited from AVLTree._clearNodes
- Defined in data-structures/binary-tree/binary-tree.ts:2306

`Protected`_clearValues

_clearValues(): void
(Protected) Clears all values from the external store.

Returns void
Remarks
Time O(N)
Inherited from AVLTree._clearValues
- Defined in data-structures/binary-tree/binary-tree.ts:2315

`Protected`_clone

_clone(cloned): void
(Protected) Helper for cloning. Performs a BFS and adds 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) add for each node).
Inherited from AVLTree._clone
- Defined in data-structures/binary-tree/binary-tree.ts:2036

`Protected`_compare

_compare(a, b): number
(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) (or O(C) if specifyComparable is used).
Inherited from AVLTree._compare
- Defined in data-structures/binary-tree/bst.ts:948

`Protected`_createInstance

_createInstance<TK, TV, TR>(options?): this
(Protected) Create an empty instance of the same concrete class.
Type Parameters
- TK = K
- TV = V
- TR extends object = R
Parameters
- Optionaloptions: Partial<AVLTreeCounterOptions<TK, TV, TR>>
  Optional constructor options for the like-kind instance.
Returns this
An empty like-kind instance.

Remarks
Time O(1), Space O(1)
Overrides AVLTree._createInstance
- Defined in data-structures/binary-tree/avl-tree-counter.ts:340

`Protected`_createLike

_createLike<TK, TV, TR>(iter?, options?): AVLTreeCounter<TK, TV, TR>
(Protected) Create a like-kind instance and seed it from an iterable.
Type Parameters
- TK = K
- TV = V
- TR extends object = R
Parameters
- iter: Iterable<
      | undefined
      | null
      | TK
      | TR
      | AVLTreeCounterNode<TK, TV>
      | [undefined | null | TK, undefined | TV], any, any> = []
  Iterable used to seed the new tree.
- Optionaloptions: Partial<AVLTreeCounterOptions<TK, TV, TR>>
  Options merged with the current snapshot.
Returns AVLTreeCounter<TK, TV, TR>
A like-kind AVLTreeCounter built from the iterable.

Remarks
Time O(N log N), Space O(N)
Overrides AVLTree._createLike
- Defined in data-structures/binary-tree/avl-tree-counter.ts:362

_createNode

_createNode(key, value?, count?): AVLTreeCounterNode<K, V>
(Protected) Creates a new AVL tree node.
Parameters
- key: K
  The key for the new node.
- Optionalvalue: V
  The value for the new node.
- Optionalcount: number
Returns AVLTreeCounterNode<K, V>
The newly created AVLTreeNode.

Remarks
Time O(1), Space O(1)
Implementation of IBinaryTree._createNode
Overrides AVLTree._createNode
- Defined in data-structures/binary-tree/avl-tree-counter.ts:136

`Protected`_DEFAULT_NODE_CALLBACK

_DEFAULT_NODE_CALLBACK(node): undefined | K
(Protected) Default callback function, returns the node's key.
Parameters
- node: undefined | null | BinaryTreeNode<K, V>
  The node.
Returns undefined | K
The node's key or undefined.

Remarks
Time O(1)
Inherited from AVLTree._DEFAULT_NODE_CALLBACK
- Defined in data-structures/binary-tree/binary-tree.ts:1942

`Protected`_dfs

_dfs<C>(callback, pattern?, onlyOne?, startNode?, iterationType?, includeNull?, shouldVisitLeft?, shouldVisitRight?, shouldVisitRoot?, shouldProcessRoot?): ReturnType<C>[]
Type Parameters
- C extends NodeCallback<BinaryTreeNode<K, V>>
  Callback type.
Parameters
- callback: C
  Function to call on nodes.
- Optionalpattern: DFSOrderPattern
  Traversal order.
- OptionalonlyOne: boolean
  Stop after first match.
- OptionalstartNode:
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V]
  Starting node.
- OptionaliterationType: IterationType
  Traversal method.
- OptionalincludeNull: boolean
  Include nulls.
- OptionalshouldVisitLeft: ((node: undefined | null | BinaryTreeNode<K, V>) => boolean)
  Predicate to traverse left.
  - - (node): boolean
    - Parameters
      node: undefined | null | BinaryTreeNode<K, V>
      Returns boolean
- OptionalshouldVisitRight: ((node: undefined | null | BinaryTreeNode<K, V>) => boolean)
  Predicate to traverse right.
  - - (node): boolean
    - Parameters
      node: undefined | null | BinaryTreeNode<K, V>
      Returns boolean
- OptionalshouldVisitRoot: ((node: undefined | null | BinaryTreeNode<K, V>) => boolean)
  Predicate to visit root.
  - - (node): boolean
    - Parameters
      node: undefined | null | BinaryTreeNode<K, V>
      Returns boolean
- OptionalshouldProcessRoot: ((node: undefined | null | BinaryTreeNode<K, V>) => boolean)
  Predicate to process root.
  - - (node): boolean
    - Parameters
      node: undefined | null | BinaryTreeNode<K, V>
      Returns boolean
Returns ReturnType<C>[]
Array of callback results.
Inherited from AVLTree._dfs
- Defined in data-structures/binary-tree/binary-tree.ts:1751

`Protected`_displayAux

_displayAux(node, options): NodeDisplayLayout
(Protected) Recursive helper for toVisual.
Parameters
- node: undefined | null | BinaryTreeNode<K, V>
  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 AVLTree._displayAux
- Defined in data-structures/binary-tree/binary-tree.ts:2061

`Protected`_ensurePredicate

_ensurePredicate(keyNodeEntryOrPredicate): NodePredicate<BinaryTreeNode<K, V>>
(Protected) Converts a key, node, entry, or predicate into a standardized predicate function.
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V]
      | NodePredicate<BinaryTreeNode<K, V>>
  The item to convert.
Returns NodePredicate<BinaryTreeNode<K, V>>
A predicate function.

Remarks
Time O(1)
Inherited from AVLTree._ensurePredicate
- Defined in data-structures/binary-tree/binary-tree.ts:2215

`Protected`_extractKey

_extractKey(keyNodeOrEntry): undefined | null | K
(Protected) Extracts the key from a key, node, or entry.
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V]
  The item.
Returns undefined | null | K
The extracted key.

Remarks
Time O(1)
Inherited from AVLTree._extractKey
- Defined in data-structures/binary-tree/binary-tree.ts:2275

`Protected`_getIterator

_getIterator(node?): IterableIterator<[K, undefined | V], any, any>
(Protected) Gets the iterator for the tree (default in-order).
Parameters
- Optionalnode: null | BinaryTreeNode<K, V> = ...
  The node to start iteration from.
Returns IterableIterator<[K, undefined | V], any, any>
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 AVLTree._getIterator
- Defined in data-structures/binary-tree/binary-tree.ts:1896

`Protected`_isPredicate

_isPredicate(p): p is NodePredicate<BinaryTreeNode<K, V>>
(Protected) Checks if an item is a predicate function.
Parameters
- p: any
  The item to check.
Returns p is NodePredicate<BinaryTreeNode<K, V>>
True if it's a function.

Remarks
Time O(1)
Inherited from AVLTree._isPredicate
- Defined in data-structures/binary-tree/binary-tree.ts:2264

`Protected`_keyValueNodeOrEntryToNodeAndValue

_keyValueNodeOrEntryToNodeAndValue(keyNodeOrEntry, value?, count?): [undefined | AVLTreeCounterNode<K, V>, undefined | V]
(Protected) Normalize input into a node plus its effective value and count.
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | AVLTreeCounterNode<K, V>
      | [undefined | null | K, undefined | V]
  Key, node, or [key, value] entry.
- Optionalvalue: V
  Value used when a bare key is provided.
- Optionalcount: number = 1
  Count increment to apply (default 1).
Returns [undefined | AVLTreeCounterNode<K, V>, undefined | V]
Tuple [node, value] where node may be undefined.

Remarks
Time O(1), Space O(1)
Overrides AVLTree._keyValueNodeOrEntryToNodeAndValue
- Defined in data-structures/binary-tree/avl-tree-counter.ts:385

`Protected`_replaceNode

_replaceNode(oldNode, newNode): AVLTreeCounterNode<K, V>
(Protected) Replace one node by another and adjust counters accordingly.
Parameters
- oldNode: AVLTreeCounterNode<K, V>
  Node being replaced.
- newNode: AVLTreeCounterNode<K, V>
  Replacement node.
Returns AVLTreeCounterNode<K, V>
The new node after replacement.

Remarks
Time O(1), Space O(1)
Overrides AVLTree._replaceNode
- Defined in data-structures/binary-tree/avl-tree-counter.ts:445

`Protected`_setRoot

_setRoot(v): void
(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 AVLTree._setRoot
- Defined in data-structures/binary-tree/bst.ts:935

`Protected`_setValue

_setValue(key, value): false | Map<K, undefined | V>
(Protected) Sets a value in the external store (Map mode).
Parameters
- key: undefined | null | K
  The key.
- value: undefined | V
  The value.
Returns false | Map<K, undefined | V>
True if successful.

Remarks
Time O(1) (average for Map.set).
Inherited from AVLTree._setValue
- Defined in data-structures/binary-tree/binary-tree.ts:2296

`Protected`_snapshotOptions

_snapshotOptions<TK, TV, TR>(): BSTOptions<TK, TV, TR>
(Protected) Snapshots the current BST's configuration options.
Type Parameters
- TK = K
- TV = V
- TR extends object = R
Returns BSTOptions<TK, TV, TR>
The options object.

Remarks
Time O(1)
Inherited from AVLTree._snapshotOptions
- Defined in data-structures/binary-tree/bst.ts:904

`Protected`_swapProperties

_swapProperties(srcNode, destNode): undefined | AVLTreeCounterNode<K, V>
(Protected) Swap keys/values/counters between the source and destination nodes.
Parameters
- srcNode: BSTNOptKeyOrNode<K, AVLTreeCounterNode<K, V>>
  Source node (or key) whose properties will be moved.
- destNode: BSTNOptKeyOrNode<K, AVLTreeCounterNode<K, V>>
  Destination node (or key) to receive properties.
Returns undefined | AVLTreeCounterNode<K, V>
Destination node after swap, or undefined.

Remarks
Time O(1), Space O(1)
Overrides AVLTree._swapProperties
- Defined in data-structures/binary-tree/avl-tree-counter.ts:410

`Protected`_updateHeight

_updateHeight(node): void
(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).
Inherited from AVLTree._updateHeight
- Defined in data-structures/binary-tree/avl-tree.ts:415

[iterator]

[iterator](...args): IterableIterator<[K, undefined | V], any, any>
Default iterator yielding [key, value] entries.
Parameters
- Rest...args: any[]
Returns IterableIterator<[K, undefined | V], any, any>
Iterator of [K, V].

Remarks
Time O(n) to iterate, Space O(1)
Implementation of IBinaryTree.[iterator]
Inherited from AVLTree.[iterator]
- Defined in data-structures/base/iterable-entry-base.ts:22

add

add(keyNodeOrEntry, value?, count?): boolean
Insert or increment a node and update aggregate count.
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | AVLTreeCounterNode<K, V>
      | [undefined | null | K, undefined | V]
  Key, node, or [key, value] entry to insert.
- Optionalvalue: V
  Value when a bare key is provided (ignored in map mode).
- Optionalcount: number = 1
  How much to increase the node's count (default 1).
Returns boolean
True if inserted/updated; false if ignored.

Remarks
Time O(log N), Space O(1)
Implementation of IBinaryTree.add
Overrides AVLTree.add
- Defined in data-structures/binary-tree/avl-tree-counter.ts:159

addMany

addMany(keysNodesEntriesOrRaws, values?, isBalanceAdd?, iterationType?): boolean[]
Adds multiple items to the tree.
Parameters
- keysNodesEntriesOrRaws: Iterable<R | BTNRep<K, V, BSTNode<K, V>>, any, any>
  An iterable of items to add.
- Optionalvalues: Iterable<undefined | V, any, any>
  An optional parallel iterable of values.
- OptionalisBalanceAdd: boolean = true
  If true, builds a balanced tree from the items.
- OptionaliterationType: IterationType = ...
  The traversal method for balanced add (recursive or iterative).
Returns boolean[]
An array of booleans indicating the success of each individual add operation.

Remarks
If isBalanceAdd is true, sorts the input and builds a balanced tree. Time O(N log N) (due to sort and balanced add). 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.
Implementation of IBinaryTree.addMany
Inherited from AVLTree.addMany
- Defined in data-structures/binary-tree/bst.ts:579

bfs

bfs<C>(callback?, startNode?, iterationType?): ReturnType<C>[]
Performs a Breadth-First Search (BFS) or Level-Order traversal.
Type Parameters
- C extends NodeCallback<BSTNode<K, V>>
  The type of the callback function.
Parameters
- Optionalcallback: C = ...
  Function to call on each node.
- OptionalstartNode:
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V] = ...
  The node to start from.
- OptionaliterationType: IterationType = ...
  The traversal method.
Returns ReturnType<C>[]
An array of callback results.

Remarks
Time O(N), visits every node. Space O(N) in the worst case for the queue.
Implementation of IBinaryTree.bfs
Inherited from AVLTree.bfs
- Defined in data-structures/binary-tree/bst.ts:349

clear

clear(): void
Remove all nodes and reset aggregate counters.

Returns void
void

Remarks
Time O(N), Space O(1)
Implementation of IBinaryTree.clear
Overrides AVLTree.clear
- Defined in data-structures/binary-tree/avl-tree-counter.ts:246

clone

clone(): this
Deep copy this tree, preserving map mode and aggregate counts.

Returns this
A deep copy of this tree.

Remarks
Time O(N), Space O(N)
Implementation of IBinaryTree.clone
Overrides AVLTree.clone
- Defined in data-structures/binary-tree/avl-tree-counter.ts:292

createTree

createTree(options?): this
Creates a new, empty tree of the same type and configuration.
Parameters
- Optionaloptions: 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 AVLTree.createTree
- Defined in data-structures/binary-tree/binary-tree.ts:404

delete

delete(keyNodeOrEntry, ignoreCount?): BinaryTreeDeleteResult<AVLTreeCounterNode<K, V>>[]
Delete a node (or decrement its count) and rebalance if needed.
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | AVLTreeCounterNode<K, V>
      | [undefined | null | K, undefined | V]
  Key, node, or [key, value] entry identifying the node.
- OptionalignoreCount: boolean = false
  If true, remove the node regardless of its count.
Returns BinaryTreeDeleteResult<AVLTreeCounterNode<K, V>>[]
Array of deletion results including deleted node and a rebalance hint when present.

Remarks
Time O(log N), Space O(1)
Implementation of IBinaryTree.delete
Overrides AVLTree.delete
- Defined in data-structures/binary-tree/avl-tree-counter.ts:182

deleteWhere

deleteWhere(predicate): boolean
Deletes the first node found that satisfies the predicate.
Parameters
- predicate: ((key: K, value: undefined | V, index: number, tree: this) => boolean)
  A function to test each [key, value] pair.
  - - (key, value, index, tree): boolean
    - Parameters
      key: K
      value: undefined | V
      index: number
      tree: this
      Returns boolean
Returns boolean
True if a node was deleted, false otherwise.

Remarks
Performs an in-order traversal. Time O(N) worst-case (O(log N) to find + O(log N) to delete). Space O(log N) for stack.
Inherited from AVLTree.deleteWhere
- Defined in data-structures/binary-tree/bst.ts:835

dfs

dfs<C>(callback?, pattern?, onlyOne?, startNode?, iterationType?): ReturnType<C>[]
Performs a Depth-First Search (DFS) traversal.
Type Parameters
- C extends NodeCallback<BSTNode<K, V>>
  The type of the callback function.
Parameters
- Optionalcallback: C = ...
  Function to call on each node.
- Optionalpattern: DFSOrderPattern = 'IN'
  The traversal order ('IN', 'PRE', 'POST').
- OptionalonlyOne: boolean = false
  If true, stops after the first callback.
- OptionalstartNode:
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V] = ...
  The node to start from.
- OptionaliterationType: IterationType = ...
  The traversal method.
Returns ReturnType<C>[]
An array of callback results.

Remarks
Time O(N), visits every node. Space O(log N) for the call/explicit stack. O(N) worst-case.
Implementation of IBinaryTree.dfs
Inherited from AVLTree.dfs
- Defined in data-structures/binary-tree/bst.ts:329

ensureNode

ensureNode(keyNodeOrEntry, iterationType?): OptNode<BSTNode<K, V>>
Ensures the input is a node. If it's a key or entry, it searches for the node.
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
  The item to resolve to a node.
- OptionaliterationType: 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 AVLTree.ensureNode
- Defined in data-structures/binary-tree/bst.ts:286

entries

entries(): IterableIterator<[K, undefined | V], any, any>
Iterate over [key, value] pairs (may yield undefined values).

Returns IterableIterator<[K, undefined | V], any, any>
Iterator of [K, V | undefined].

Remarks
Time O(n), Space O(1)
Implementation of IBinaryTree.entries
Inherited from AVLTree.entries
- Defined in data-structures/base/iterable-entry-base.ts:31

every

every(predicate, thisArg?): boolean
Test whether all entries satisfy the predicate.
Parameters
- predicate: EntryCallback<K, undefined | V, boolean>
  (key, value, index, self) => boolean.
- OptionalthisArg: any
  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 AVLTree.every
- Defined in data-structures/base/iterable-entry-base.ts:66

filter

filter(predicate, thisArg?): this
Creates a new tree containing only the entries that satisfy the predicate.
Parameters
- predicate: EntryCallback<K, undefined | V, boolean>
  A function to test each [key, value] pair.
- OptionalthisArg: 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) add for each item). Space O(N) for the new tree.
Implementation of IBinaryTree.filter
Inherited from AVLTree.filter
- Defined in data-structures/binary-tree/binary-tree.ts:1673

find

find(callbackfn, thisArg?): undefined | [K, undefined | V]
Find the first entry that matches a predicate.
Parameters
- callbackfn: EntryCallback<K, undefined | V, boolean>
  (key, value, index, self) => boolean.
- OptionalthisArg: any
  Optional this for callback.
Returns undefined | [K, undefined | V]
Matching [key, value] or undefined.

Remarks
Time O(n), Space O(1)
Implementation of IBinaryTree.find
Inherited from AVLTree.find
- Defined in data-structures/base/iterable-entry-base.ts:114

forEach

forEach(callbackfn, thisArg?): void
Visit each entry, left-to-right.
Parameters
- callbackfn: EntryCallback<K, undefined | V, void>
  (key, value, index, self) => void.
- OptionalthisArg: any
  Optional this for callback.
Returns void
Remarks
Time O(n), Space O(1)
Implementation of IBinaryTree.forEach
Inherited from AVLTree.forEach
- Defined in data-structures/base/iterable-entry-base.ts:99

get

get(keyNodeEntryOrPredicate, startNode?, iterationType?): undefined | V
Gets the value associated with a key.
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V]
  The key, node, or entry to get the value for.
- OptionalstartNode:
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V] = ...
  The node to start searching from (if not in Map mode).
- OptionaliterationType: IterationType = ...
  The traversal method (if not in Map mode).
Returns undefined | V
The associated value, or undefined.

Remarks
Time O(log N), For BST, Red-Black Tree, and AVL Tree subclasses, the worst-case time is O(log N). Time O(1) if in Map mode. O(N) if not in Map mode (uses getNode). Space O(1) if in Map mode. O(H) or O(N) otherwise.
Implementation of IBinaryTree.get
Inherited from AVLTree.get
- Defined in data-structures/binary-tree/binary-tree.ts:884

getComputedCount

getComputedCount(): number
Compute the total count by traversing the tree (sums node.count).

Returns number
Total count recomputed from nodes.

Remarks
Time O(N), Space O(H)
- Defined in data-structures/binary-tree/avl-tree-counter.ts:130

getDepth

getDepth(dist, startNode?): number
Gets the depth of a node (distance from startNode).
Parameters
- dist:
      | undefined
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V]
  The node to find the depth of.
- OptionalstartNode:
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V] = ...
  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).
Implementation of IBinaryTree.getDepth
Inherited from AVLTree.getDepth
- Defined in data-structures/binary-tree/binary-tree.ts:1023

getHeight

getHeight(startNode?, iterationType?): number
Gets the maximum height of the tree (longest path from startNode to a leaf).
Parameters
- OptionalstartNode:
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V] = ...
  The node to start measuring from.
- OptionaliterationType: 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).
Implementation of IBinaryTree.getHeight
Inherited from AVLTree.getHeight
- Defined in data-structures/binary-tree/binary-tree.ts:1048

getLeftMost

getLeftMost<C>(callback?, startNode?, iterationType?): ReturnType<C>
Finds the leftmost node in a subtree (the node with the smallest key in a BST).
Type Parameters
- C extends NodeCallback<undefined | BinaryTreeNode<K, V>>
  The type of the callback function.
Parameters
- Optionalcallback: C = ...
  A function to call on the leftmost node.
- OptionalstartNode:
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V] = ...
  The subtree root to search from.
- OptionaliterationType: IterationType = ...
  The traversal method.
Returns ReturnType<C>
The callback result for the leftmost node.

Remarks
Time O(H), where H is the height of the left spine. O(N) worst-case. Space O(H) for recursive/trampoline stack.
Implementation of IBinaryTree.getLeftMost
Inherited from AVLTree.getLeftMost
- Defined in data-structures/binary-tree/binary-tree.ts:1175

getMinHeight

getMinHeight(startNode?, iterationType?): number
Gets the minimum height of the tree (shortest path from startNode to a leaf).
Parameters
- OptionalstartNode:
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V] = ...
  The node to start measuring from.
- OptionaliterationType: 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 AVLTree.getMinHeight
- Defined in data-structures/binary-tree/binary-tree.ts:1090

getNode

getNode(keyNodeEntryOrPredicate, startNode?, iterationType?): OptNode<BSTNode<K, V>>
Gets the first node matching a predicate.
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
      | NodePredicate<BSTNode<K, V>>
  The key, node, entry, or predicate function to search for.
- OptionalstartNode: BSTNOptKeyOrNode<K, BSTNode<K, V>> = ...
  The node to start the search from.
- OptionaliterationType: 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).
Implementation of IBinaryTree.getNode
Inherited from AVLTree.getNode
- Defined in data-structures/binary-tree/bst.ts:384

getNodes

getNodes(keyNodeEntryOrPredicate, onlyOne?, startNode?, iterationType?): BinaryTreeNode<K, V>[]
Gets all nodes matching a predicate.
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V]
      | NodePredicate<BinaryTreeNode<K, V>>
  The key, node, entry, or predicate function to search for.
- OptionalonlyOne: boolean
  If true, stops after finding the first match.
- OptionalstartNode:
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V]
  The node to start the search from.
- OptionaliterationType: 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).
Inherited from AVLTree.getNodes
- Defined in data-structures/binary-tree/binary-tree.ts:824

getPathToRoot

getPathToRoot<C>(beginNode, callback?, isReverse?): ReturnType<C>[]
Gets the path from a given node up to the root.
Type Parameters
- C extends NodeCallback<undefined | BinaryTreeNode<K, V>>
  The type of the callback function.
Parameters
- beginNode:
      | undefined
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V]
  The node to start the path from.
- Optionalcallback: C = ...
  A function to call on each node in the path.
- OptionalisReverse: boolean = false
  If true, returns the path from root-to-node.
Returns ReturnType<C>[]
An array of callback results.

Remarks
Time O(H), where H is the depth of the beginNode. O(N) worst-case. Space O(H) for the result array.
Implementation of IBinaryTree.getPathToRoot
Inherited from AVLTree.getPathToRoot
- Defined in data-structures/binary-tree/binary-tree.ts:1147

getPredecessor

getPredecessor(node): BinaryTreeNode<K, V>
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 AVLTree.getPredecessor
- Defined in data-structures/binary-tree/binary-tree.ts:1249

getRightMost

getRightMost<C>(callback?, startNode?, iterationType?): ReturnType<C>
Finds the rightmost node in a subtree (the node with the largest key in a BST).
Type Parameters
- C extends NodeCallback<undefined | BinaryTreeNode<K, V>>
  The type of the callback function.
Parameters
- Optionalcallback: C = ...
  A function to call on the rightmost node.
- OptionalstartNode:
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V] = ...
  The subtree root to search from.
- OptionaliterationType: IterationType = ...
  The traversal method.
Returns ReturnType<C>
The callback result for the rightmost node.

Remarks
Time O(H), where H is the height of the right spine. O(N) worst-case. Space O(H) for recursive/trampoline stack.
Implementation of IBinaryTree.getRightMost
Inherited from AVLTree.getRightMost
- Defined in data-structures/binary-tree/binary-tree.ts:1214

getSuccessor

getSuccessor(x?): undefined | null | BinaryTreeNode<K, V>
Gets the in-order successor of a node in a BST.
Parameters
- Optionalx: null | K | BinaryTreeNode<K, V>
  The node to find the successor of.
Returns undefined | null | BinaryTreeNode<K, V>
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 AVLTree.getSuccessor
- Defined in data-structures/binary-tree/binary-tree.ts:1270

has

has(keyNodeEntryOrPredicate?, startNode?, iterationType?): boolean
Checks if a node matching the predicate exists in the tree.
Parameters
- OptionalkeyNodeEntryOrPredicate:
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V]
      | NodePredicate<BinaryTreeNode<K, V>>
  The key, node, entry, or predicate to check for.
- OptionalstartNode:
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V]
  The node to start the search from.
- OptionaliterationType: IterationType
  The traversal method.
Returns boolean
True if a matching node exists, false otherwise.

Remarks
Time O(log N), For BST, Red-Black Tree, and AVL Tree subclasses, the worst-case time is O(log N). Time O(N) in the worst case (via search). Space O(H) or O(N) (via search).
Implementation of IBinaryTree.has
Inherited from AVLTree.has
- Defined in data-structures/binary-tree/binary-tree.ts:906

hasValue

hasValue(value): boolean
Whether there exists an entry with the given value.
Parameters
- value: undefined | V
  Value to test.
Returns boolean
true if found; otherwise false.

Remarks
Time O(n), Space O(1)
Implementation of IBinaryTree.hasValue
Inherited from AVLTree.hasValue
- Defined in data-structures/base/iterable-entry-base.ts:143

isAVLBalanced

isAVLBalanced(iterationType?): boolean
Checks if the tree meets the AVL balance condition (height difference <= 1).
Parameters
- OptionaliterationType: 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.
Inherited from AVLTree.isAVLBalanced
- Defined in data-structures/binary-tree/bst.ts:757

isBST

isBST(startNode?, iterationType?): boolean
Checks if the tree is a valid Binary Search Tree (BST).
Parameters
- OptionalstartNode:
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V] = ...
  The node to start checking from.
- OptionaliterationType: 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).
Implementation of IBinaryTree.isBST
Inherited from AVLTree.isBST
- Defined in data-structures/binary-tree/binary-tree.ts:972

isEmpty

isEmpty(): boolean
Checks if the tree is empty.

Returns boolean
True if the tree has no nodes, false otherwise.

Remarks
Time O(1), Space O(1)
Implementation of IBinaryTree.isEmpty
Inherited from AVLTree.isEmpty
- Defined in data-structures/binary-tree/binary-tree.ts:947

isEntry

isEntry(keyNodeOrEntry): keyNodeOrEntry is BTNEntry<K, V>
Checks if the given item is a [key, value] entry pair.
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V]
  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 AVLTree.isEntry
- Defined in data-structures/binary-tree/binary-tree.ts:541

isLeaf

isLeaf(keyNodeOrEntry): boolean
Checks if a node is a leaf (has no real children).
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V]
  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 AVLTree.isLeaf
- Defined in data-structures/binary-tree/binary-tree.ts:527

isNIL

isNIL(keyNodeOrEntry): boolean
Checks if the given item is the sentinel NIL node.
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V]
  The item to check.
Returns boolean
True if it's the NIL node, false otherwise.

Remarks
Time O(1), Space O(1)
Inherited from AVLTree.isNIL
- Defined in data-structures/binary-tree/binary-tree.ts:496

isNode

isNode(keyNodeOrEntry): keyNodeOrEntry is AVLTreeCounterNode<K, V>
Type guard: check whether the input is an AVLTreeCounterNode.
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | AVLTreeCounterNode<K, V>
      | [undefined | null | K, undefined | V]
Returns keyNodeOrEntry is AVLTreeCounterNode<K, V>
True if the value is an AVLTreeCounterNode.

Remarks
Time O(1), Space O(1)
Overrides AVLTree.isNode
- Defined in data-structures/binary-tree/avl-tree-counter.ts:145

isPerfectlyBalanced

isPerfectlyBalanced(startNode?): boolean
Checks if the tree is perfectly balanced.
Parameters
- OptionalstartNode:
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V] = ...
  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 AVLTree.isPerfectlyBalanced
- Defined in data-structures/binary-tree/binary-tree.ts:958

isRange

isRange(keyNodeEntryOrPredicate): keyNodeEntryOrPredicate is Range<K>
Checks if the given item is a Range object.
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V]
      | NodePredicate<BinaryTreeNode<K, V>>
      | Range<K>
  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 AVLTree.isRange
- Defined in data-structures/binary-tree/binary-tree.ts:507

isRaw

isRaw(keyNodeEntryOrRaw): keyNodeEntryOrRaw is R
Checks if the given item is a raw data object (R) that needs conversion via toEntryFn.
Parameters
- keyNodeEntryOrRaw:
      | undefined
      | null
      | K
      | R
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V]
  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 AVLTree.isRaw
- Defined in data-structures/binary-tree/binary-tree.ts:456

isRealNode

isRealNode(keyNodeOrEntry): keyNodeOrEntry is BinaryTreeNode<K, V>
Checks if the given item is a "real" node (i.e., not null, undefined, or NIL).
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V]
  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 AVLTree.isRealNode
- Defined in data-structures/binary-tree/binary-tree.ts:469

isRealNodeOrNull

isRealNodeOrNull(keyNodeOrEntry): keyNodeOrEntry is null | BinaryTreeNode<K, V>
Checks if the given item is either a "real" node or null.
Parameters
- keyNodeOrEntry:
      | undefined
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V]
  The item to check.
Returns keyNodeOrEntry is null | BinaryTreeNode<K, V>
True if it's a real node or null, false otherwise.

Remarks
Time O(1), Space O(1)
Inherited from AVLTree.isRealNodeOrNull
- Defined in data-structures/binary-tree/binary-tree.ts:483

isValidKey

isValidKey(key): key is K
Checks if the given key is valid (comparable).
Parameters
- key: any
  The key to validate.
Returns key is K
True if the key is valid, false otherwise.

Remarks
Time O(1)
Inherited from AVLTree.isValidKey
- Defined in data-structures/binary-tree/bst.ts:313

keys

keys(): IterableIterator<K, any, any>
Iterate over keys only.

Returns IterableIterator<K, any, any>
Iterator of keys.

Remarks
Time O(n), Space O(1)
Implementation of IBinaryTree.keys
Inherited from AVLTree.keys
- Defined in data-structures/base/iterable-entry-base.ts:42

leaves

leaves<C>(callback?, startNode?, iterationType?): ReturnType<C>[]
Finds all leaf nodes in the tree.
Type Parameters
- C extends NodeCallback<null | BinaryTreeNode<K, V>>
  The type of the callback function.
Parameters
- Optionalcallback: C = ...
  Function to call on each leaf node.
- OptionalstartNode:
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V] = ...
  The node to start from.
- OptionaliterationType: IterationType = ...
  The traversal method.
Returns ReturnType<C>[]
An array of callback results.

Remarks
Time O(N), visits every node. Space O(H) for recursive stack or O(N) for iterative queue.
Implementation of IBinaryTree.leaves
Inherited from AVLTree.leaves
- Defined in data-structures/binary-tree/binary-tree.ts:1421

lesserOrGreaterTraverse

lesserOrGreaterTraverse<C>(callback?, lesserOrGreater?, targetNode?, iterationType?): ReturnType<C>[]
Traverses the tree and returns nodes that are lesser or greater than a target node.
Type Parameters
- C extends NodeCallback<BSTNode<K, V>>
  The type of the callback function.
Parameters
- Optionalcallback: C = ...
  Function to call on matching nodes.
- OptionallesserOrGreater: CP = -1
  1 for lesser, 1 for greater, 0 for equal.
- OptionaltargetNode:
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V] = ...
  The node to compare against.
- OptionaliterationType: IterationType = ...
  The traversal method.
Returns ReturnType<C>[]
An array of callback results.

Remarks
Time O(N), as it performs a full traversal. Space O(log N) or O(N).
Inherited from AVLTree.lesserOrGreaterTraverse
- Defined in data-structures/binary-tree/bst.ts:681

listLevels

listLevels<C>(callback?, startNode?, iterationType?): ReturnType<C>[][]
Returns a 2D array of nodes, grouped by level.
Type Parameters
- C extends NodeCallback<BSTNode<K, V>>
  The type of the callback function.
Parameters
- Optionalcallback: C = ...
  Function to call on each node.
- OptionalstartNode:
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V] = ...
  The node to start from.
- OptionaliterationType: IterationType = ...
  The traversal method.
Returns ReturnType<C>[][]
A 2D array of callback results.

Remarks
Time O(N), visits every node. Space O(N) for the result array and the queue/stack.
Implementation of IBinaryTree.listLevels
Inherited from AVLTree.listLevels
- Defined in data-structures/binary-tree/bst.ts:367

map

map<MK, MV, MR>(callback, options?, thisArg?): AVLTreeCounter<MK, MV, MR>
Create a new AVLTreeCounter by mapping each [key, value] entry.
Type Parameters
- MK = K
- MV = V
- MR extends object = object
Parameters
- callback: EntryCallback<K, undefined | V, [MK, MV]>
  Function mapping (key, value, index, tree) → [newKey, newValue].
- Optionaloptions: Partial<BinaryTreeOptions<MK, MV, MR>>
  Options for the output tree.
- OptionalthisArg: unknown
  Value for this inside the callback.
Returns AVLTreeCounter<MK, MV, MR>
A new AVLTreeCounter with mapped entries.

Remarks
Time O(N log N), Space O(N)
Implementation of IBinaryTree.map
Overrides AVLTree.map
- Defined in data-structures/binary-tree/avl-tree-counter.ts:317

merge

merge(anotherTree): void
Merges another tree into this one by adding all its nodes.
Parameters
- anotherTree: BinaryTree<K, V, R>
  The tree to merge.
Returns void
Remarks
Time O(N * M), same as addMany, where N is the size of anotherTree and M is the size of this tree. Space O(M) (from add).
Implementation of IBinaryTree.merge
Inherited from AVLTree.merge
- Defined in data-structures/binary-tree/binary-tree.ts:665

morris

morris<C>(callback?, pattern?, startNode?): ReturnType<C>[]
Type Parameters
- C extends NodeCallback<BinaryTreeNode<K, V>>
  The type of the callback function.
Parameters
- Optionalcallback: C
  Function to call on each node.
- Optionalpattern: DFSOrderPattern
  The traversal order ('IN', 'PRE', 'POST').
- OptionalstartNode:
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V]
  The node to start from.
Returns ReturnType<C>[]
An array of callback results.
Implementation of IBinaryTree.morris
Inherited from AVLTree.morris
- Defined in data-structures/binary-tree/binary-tree.ts:1537

perfectlyBalance

perfectlyBalance(iterationType?): boolean
Rebuild the tree into a perfectly balanced form using in-order nodes.
Parameters
- OptionaliterationType: IterationType = ...
  Traversal style to use when constructing the balanced tree.
Returns boolean
True if rebalancing succeeded (tree not empty).

Remarks
Time O(N), Space O(N)
Overrides AVLTree.perfectlyBalance
- Defined in data-structures/binary-tree/avl-tree-counter.ts:257

print

print(options?, startNode?): void
Prints a visual representation of the tree to the console.
Parameters
- Optionaloptions: BinaryTreePrintOptions
  Options to control the output.
- OptionalstartNode:
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V] = ...
  The node to start printing from.
Returns void
Remarks
Time O(N) (via toVisual). Space O(N*H) or O(N^2) (via toVisual).
Inherited from AVLTree.print
- Defined in data-structures/binary-tree/binary-tree.ts:1744

rangeSearch

rangeSearch<C>(range, callback?, startNode?, iterationType?): ReturnType<C>[]
Performs an optimized search for nodes within a given key range.
Type Parameters
- C extends NodeCallback<BSTNode<K, V>>
  The type of the callback function.
Parameters
- range: Range<K> | [K, K]
  A Range object or a [low, high] tuple.
- Optionalcallback: C = ...
  A function to call on matching nodes.
- OptionalstartNode:
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V] = ...
  The node to start the search from.
- OptionaliterationType: IterationType = ...
  The traversal method.
Returns ReturnType<C>[]
An array of callback results.

Remarks
Time O(H + M), where H is tree height and M is the number of matches.
Inherited from AVLTree.rangeSearch
- Defined in data-structures/binary-tree/bst.ts:505

reduce

reduce<U>(callbackfn, initialValue): U
Reduce entries into a single accumulator.
Type Parameters
- U
Parameters
- callbackfn: ReduceEntryCallback<K, undefined | V, 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 AVLTree.reduce
- Defined in data-structures/base/iterable-entry-base.ts:171

refill

refill(keysNodesEntriesOrRaws, values?): void
Clears the tree and refills it with new items.
Parameters
- keysNodesEntriesOrRaws: Iterable<
      | undefined
      | null
      | K
      | R
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V], any, any>
  An iterable of items to add.
- Optionalvalues: Iterable<undefined | V, any, any>
  An optional parallel iterable of values.
Returns void
Remarks
Time O(N) (for clear) + O(N * M) (for addMany) = O(N * M). Space O(M) (from addMany).
Implementation of IBinaryTree.refill
Inherited from AVLTree.refill
- Defined in data-structures/binary-tree/binary-tree.ts:676

search

search<C>(keyNodeEntryOrPredicate, onlyOne?, callback?, startNode?, iterationType?): ReturnType<C>[]
Searches the tree for nodes matching a predicate, key, or range.
Type Parameters
- C extends NodeCallback<BSTNode<K, V>>
  The type of the callback function.
Parameters
- keyNodeEntryOrPredicate:
      | undefined
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V]
      | NodePredicate<BSTNode<K, V>>
      | Range<K>
  The key, node, entry, predicate, or range to search for.
- OptionalonlyOne: boolean = false
  If true, stops after finding the first match.
- Optionalcallback: C = ...
  A function to call on matching nodes.
- OptionalstartNode:
      | null
      | K
      | BSTNode<K, V>
      | [undefined | null | K, undefined | V] = ...
  The node to start the search from.
- OptionaliterationType: IterationType = ...
  Whether to use 'RECURSIVE' or 'ITERATIVE' search.
Returns ReturnType<C>[]
An array of results from the callback function for each matching node.

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.
Implementation of IBinaryTree.search
Inherited from AVLTree.search
- Defined in data-structures/binary-tree/bst.ts:412

some

some(predicate, thisArg?): boolean
Test whether any entry satisfies the predicate.
Parameters
- predicate: EntryCallback<K, undefined | V, boolean>
  (key, value, index, self) => boolean.
- OptionalthisArg: any
  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 AVLTree.some
- Defined in data-structures/base/iterable-entry-base.ts:83

toVisual

toVisual(startNode?, options?): string
Generates a string representation of the tree for visualization.
Parameters
- OptionalstartNode:
      | null
      | K
      | BinaryTreeNode<K, V>
      | [undefined | null | K, undefined | V] = ...
  The node to start printing from.
- Optionaloptions: 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 AVLTree.toVisual
- Defined in data-structures/binary-tree/binary-tree.ts:1711

values

values(): IterableIterator<undefined | V, any, any>
Iterate over values only.

Returns IterableIterator<undefined | V, any, any>
Iterator of values.

Remarks
Time O(n), Space O(1)
Implementation of IBinaryTree.values
Inherited from AVLTree.values
- Defined in data-structures/base/iterable-entry-base.ts:53

Class AVLTreeCounter<K, V, R>

Remarks

Type Parameters

Hierarchy (view full)

Implements

Index

Constructors

Properties

Accessors

Methods

Constructors

constructor

Type Parameters

Parameters

Returns AVLTreeCounter<K, V, R>

Remarks

Properties

Protected_comparator

Remarks

Accessors

comparator

Returns Comparator<K>

Remarks

isDuplicate

Returns boolean

Remarks

isMapMode

Returns boolean

Remarks

isReverse

Returns boolean

Remarks

NIL

Returns BinaryTreeNode<K, V>

Remarks

root

Returns OptNode<BSTNode<K, V>>

Remarks

size

Returns number

Remarks

specifyComparable

Returns undefined | ((key: K) => Comparable)

Remarks

store

Returns Map<K, undefined | V>

Remarks

toEntryFn

Returns undefined | ToEntryFn<K, V, R>

Remarks

Methods

Protected_balanceFactor

Parameters

Returns number

Remarks

Protected_balanceLL

Parameters

Returns void

Remarks

Protected_balanceLR

Parameters

Returns void

Remarks

Protected_balancePath

Parameters

Returns void

Remarks

Protected_balanceRL

Parameters

Returns void

Remarks

Protected_balanceRR

Parameters

Returns void

Remarks

Protected_clearNodes

Returns void

Remarks

Protected_clearValues

Returns void

`Protected`_comparator

`Protected`_balanceFactor

`Protected`_balanceLL

`Protected`_balanceLR

`Protected`_balancePath

`Protected`_balanceRL

`Protected`_balanceRR

`Protected`_clearNodes

`Protected`_clearValues

`Protected`_clone

`Protected`_compare

`Protected`_createInstance

`Protected`_createLike

`Protected`_DEFAULT_NODE_CALLBACK

`Protected`_dfs

`Protected`_displayAux

`Protected`_ensurePredicate

`Protected`_extractKey

`Protected`_getIterator

`Protected`_isPredicate

`Protected`_keyValueNodeOrEntryToNodeAndValue

`Protected`_replaceNode

`Protected`_setRoot