Class BST<K, V, R, MK, MV, MR>

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

Example

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

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

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

Example

// Find elements in a range
    const bst = new BST<number>([10, 5, 15, 3, 7, 12, 18]);
    console.log(bst.search(new Range(5, 10))); // [5, 7, 10]
    console.log(bst.rangeSearch([4, 12], node => node.key.toString())); // ['5', '7', '10', '12']
    console.log(bst.search(new Range(4, 12, true, false))); // [5, 7, 10]
    console.log(bst.rangeSearch([15, 20])); // [15, 18]
    console.log(bst.search(new Range(15, 20, false))); // [18]

Example

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

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

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

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

Type Parameters

  • K = any
  • V = any
  • R = object
  • MK = any
  • MV = any
  • MR = object

Hierarchy (view full)

Implements

Constructors

constructor

Methods

_clearNodes _clearValues _compare _dfs _displayAux _ensurePredicate _extractKey _getIterator _isPredicate _keyValueNodeOrEntryToNodeAndValue _replaceNode _setRoot _setValue _swapProperties [iterator] add addMany bfs clear clone createNode createTree delete dfs ensureNode entries every filter find forEach get getDepth getHeight getLeftMost getMinHeight getNode getNodes getPathToRoot getPredecessor getRightMost getSuccessor has hasValue isAVLBalanced isBST isEmpty isEntry isLeaf isNIL isNode isPerfectlyBalanced isRange isRaw isRealNode isRealNodeOrNull isValidKey keys leaves lesserOrGreaterTraverse listLevels map merge morris perfectlyBalance print rangeSearch reduce refill search some toVisual values

Constructors

constructor

  • new BST<K, V, R, MK, MV, MR>(keysNodesEntriesOrRaws?, options?): BST<K, V, R, MK, MV, MR>

  • This TypeScript constructor initializes a binary search tree with optional options and adds elements if provided.

    Type Parameters

    • K = any
    • V = any
    • R = object
    • MK = any
    • MV = any
    • MR = object

    Parameters

    • keysNodesEntriesOrRaws: Iterable<
          | undefined
          | null
          | K
          | R
          | BSTNode<K, V>
          | [undefined | null | K, undefined | V], any, any> = []

      The keysNodesEntriesOrRaws parameter in the constructor is an iterable that can contain elements of type K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined or R. It is used to initialize the binary search tree with keys, nodes, entries, or raw data.

    • Optionaloptions: BSTOptions<K, V, R>

      The options parameter is an optional object that can contain the following properties:

    Returns BST<K, V, R, MK, MV, MR>

Methods

Protected_clearNodes

Protected_clearValues

Protected_compare

  • _compare(a, b): number

  • Time Complexity: O(1) Space Complexity: O(1)

    The _compare function compares two values using a specified comparator function and optionally reverses the result.

    Parameters

    • a: K

      The parameter a is of type K, which is used as an input for comparison in the _compare method.

    • b: K

      The parameter b in the _compare function is of type K.

    Returns number

    The _compare method is returning the result of the ternary expression. If _isReverse is true, it returns the negation of the result of calling the _comparator function with arguments a and b. If _isReverse is false, it returns the result of calling the _comparator function with arguments a and b.

Protected_dfs

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

  • Type Parameters

    Parameters

    • callback: C

      The callback parameter in the _dfs method is a function that will be called on each node visited during the depth-first search traversal. It is a generic type C that extends NodeCallback<BinaryTreeNode<K, V> | null>. The default value for callback

    • Optionalpattern: DFSOrderPattern

      The pattern parameter in the _dfs method specifies the order in which the nodes are visited during a depth-first search traversal. It can have one of the following values:

    • OptionalonlyOne: boolean

      The onlyOne parameter in the _dfs method is a boolean flag that determines whether the traversal should stop after processing a single node. If onlyOne is set to true, the traversal will return as soon as a single node is processed. If it is set to false @param {K | BinaryTreeNode<K, V> | [K | null | undefined, V | undefined] | null | undefined} startNode - The startNodeparameter in the_dfsmethod is used to specify the starting node for the depth-first search traversal. It can be provided in different forms: @param {IterationType} iterationType - TheiterationTypeparameter in the_dfsmethod specifies whether the traversal should be done recursively or iteratively. It can have two possible values: @param [includeNull=false] - TheincludeNullparameter in the_dfsmethod determines whether null nodes should be included in the traversal process. IfincludeNullis set totrue, the method will consider null nodes as valid nodes to visit or process. If includeNullis set tofalse, @param shouldVisitLeft - The shouldVisitLeftparameter in the_dfsmethod is a function that determines whether the left child of a node should be visited during the Depth-First Search traversal. By default, it checks if the node is not null or undefined before visiting the left child. You can customize this behavior @param shouldVisitRight - TheshouldVisitRightparameter in the_dfsmethod is a function that determines whether to visit the right child node of the current node during a depth-first search traversal. The default implementation of this function checks if the node is not null or undefined before deciding to visit it. @param shouldVisitRoot - TheshouldVisitRootparameter in the_dfsmethod is a function that determines whether a given node should be visited during the depth-first search traversal. The function takes a node as an argument and returns a boolean value indicating whether the node should be visited. @param shouldProcessRoot - TheshouldProcessRootparameter in the_dfsmethod is a function that determines whether the root node should be processed during the Depth-First Search traversal. It takes a node (BinaryTreeNode<K, V> | null | undefined) as input and returns a boolean value. If the function @returns The_dfsmethod returns an array of the return type of the provided callback functionC`.

    • OptionalstartNode:
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]
    • OptionaliterationType: IterationType
    • OptionalincludeNull: boolean
    • OptionalshouldVisitLeft: ((node: undefined | null | BinaryTreeNode<K, V>) => boolean)
        • (node): boolean

        • Parameters

          Returns boolean

    • OptionalshouldVisitRight: ((node: undefined | null | BinaryTreeNode<K, V>) => boolean)
        • (node): boolean

        • Parameters

          Returns boolean

    • OptionalshouldVisitRoot: ((node: undefined | null | BinaryTreeNode<K, V>) => boolean)
        • (node): boolean

        • Parameters

          Returns boolean

    • OptionalshouldProcessRoot: ((node: undefined | null | BinaryTreeNode<K, V>) => boolean)
        • (node): boolean

        • Parameters

          Returns boolean

    Returns ReturnType<C>[]

Protected_displayAux

  • _displayAux(node, options): NodeDisplayLayout

  • Time Complexity: O(n) Space Complexity: O(n)

    The function _displayAux in TypeScript is responsible for generating the display layout of nodes in a binary tree based on specified options.

    Parameters

    • node: undefined | null | BinaryTreeNode<K, V>

      The node parameter in the _displayAux function represents a node in a binary tree. It can be either a valid node containing a key or a special type of node like null, undefined, or a Red-Black tree NIL node. The function checks the type of the node and its

    • options: BinaryTreePrintOptions

      The options parameter in the _displayAux function contains the following properties:

    Returns NodeDisplayLayout

    The _displayAux function returns a NodeDisplayLayout, which is an array containing information about how to display a node in a binary tree. The NodeDisplayLayout consists of four elements:

Protected_ensurePredicate

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

  • Parameters

    • keyNodeEntryOrPredicate:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]
          | NodePredicate<BinaryTreeNode<K, V>>

      The _ensurePredicate method in the provided code snippet is responsible for ensuring that the input parameter keyNodeEntryOrPredicate is transformed into a valid predicate function that can be used for filtering nodes in a binary tree.

    Returns NodePredicate<BinaryTreeNode<K, V>>

    A NodePredicate<BinaryTreeNode<K, V>> function is being returned.

Protected_extractKey

  • _extractKey(keyNodeOrEntry): undefined | null | K

  • Time Complexity: O(1) Space Complexity: O(1)

    The function _extractKey in TypeScript returns the key from a given input, which can be a node, entry, raw data, or null/undefined.

    Parameters

    • keyNodeOrEntry:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]

      The _extractKey method you provided is a TypeScript method that takes in a parameter keyNodeOrEntry of type K | BinaryTreeNode<K, V> | [K | null | undefined, V | undefined] | null | undefined , where BTNRep is a generic type with keys K, V, and BinaryTreeNode<K, V>, and @returns The_extractKeymethod returns the key value extracted from thekeyNodeOrEntryparameter. The return value can be a key value of typeK, null, or undefined`, depending on the conditions checked in the method.

    Returns undefined | null | K

Protected_getIterator

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

  • Time Complexity: O(1) Space Complexity: O(1)

    The function _getIterator returns an iterable iterator for a binary tree data structure, either using an iterative approach or a recursive approach based on the specified iteration type.

    Parameters

    • node: undefined | null | BinaryTreeNode<K, V> = ...

      The node parameter in the _getIterator method represents the current node being processed during iteration. It is initially set to the root node of the data structure (or the node passed as an argument), and then it is traversed through the data structure based on the iteration type specified (ITER @returns The _getIteratormethod returns an IterableIterator containing key-value pairs of nodes in a binary tree structure. The method uses an iterative approach to traverse the tree based on theiterationTypeproperty. If theiterationTypeis set to 'ITERATIVE', the method uses a stack to perform an in-order traversal of the tree. If theiterationType` is not 'ITERATIVE

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

Protected_isPredicate

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

  • Time Complexity: O(1) Space Complexity: O(1)

    The function _isPredicate checks if a given parameter is a function.

    Parameters

    • p: any

      The parameter p is a variable of type any, which means it can hold any type of value. In this context, the function _isPredicate is checking if p is a function that satisfies the type NodePredicate<BinaryTreeNode<K, V>>.

    Returns p is NodePredicate<BinaryTreeNode<K, V>>

    The function is checking if the input p is a function and returning a boolean value based on that check. If p is a function, it will return true, indicating that p is a predicate function for a binary tree node. If p is not a function, it will return false.

Protected_keyValueNodeOrEntryToNodeAndValue

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

  • Time Complexity: O(1) Space Complexity: O(1)

    The function overrides a method and converts a key, value pair or entry or raw element to a node.

    Parameters

    • keyNodeOrEntry:
          | undefined
          | null
          | K
          | BSTNode<K, V>
          | [undefined | null | K, undefined | V]

      A variable that can be of type R or K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined . It represents either a key, a node, an entry, or a raw element.

    • Optionalvalue: V

      The value parameter is an optional value of type V. It represents the value associated with a key in a key-value pair.

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

    either a BSTNode<K, V> object or undefined.

Protected_replaceNode

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

  • Time Complexity: O(1) Space Complexity: O(1)

    The _replaceNode function replaces an old node with a new node in a binary tree structure.

    Parameters

    • oldNode: BinaryTreeNode<K, V>

      The oldNode parameter represents the node that you want to replace in a tree data structure.

    • newNode: BinaryTreeNode<K, V>

      The newNode parameter in the _replaceNode function represents the node that will replace the oldNode in a tree data structure. This function is responsible for updating the parent, left child, right child, and root (if necessary) references when replacing a node in the tree.

    Returns BinaryTreeNode<K, V>

    The method _replaceNode is returning the newNode that was passed as a parameter after replacing the oldNode with it in the binary tree structure.

Protected_setRoot

  • _setRoot(v): void

  • Time Complexity: O(1) Space Complexity: O(1)

    The function sets the root of a tree-like structure and updates the parent property of the new root.

    Parameters

    • v: OptNode<BSTNode<K, V>>

      v is a parameter of type BSTNode<K, V> or undefined.

    Returns void

Protected_setValue

  • _setValue(key, value): false | Map<K, undefined | V>

  • Time Complexity: O(1) Space Complexity: O(1)

    The function _setValue sets a value in a store based on a key, handling cases where the key or value is null or undefined.

    Parameters

    • key: undefined | null | K

      The key parameter can be of type K, null, or undefined.

    • value: undefined | V

      The value parameter in the _setValue method can be of type V or undefined.

    Returns false | Map<K, undefined | V>

    The method _setValue returns false if either the key is null or undefined, or if the value is undefined. Otherwise, it returns the result of calling the set method on the _store object with the key and value arguments.

Protected_swapProperties

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

  • Time Complexity: O(1) Space Complexity: O(1)

    The _swapProperties function swaps key and value properties between two nodes in a binary tree.

    Parameters

    • srcNode:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]

      The srcNode parameter in the _swapProperties method can be either a BTNRep object containing key and value properties, or it can be of type R.

    • destNode:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]

      The destNode parameter in the _swapProperties method represents the node or entry where the properties will be swapped with the srcNode. It can be of type K | BinaryTreeNode<K, V> | [K | null | undefined, V | undefined] | null | undefined or R. The method ensures that both srcNode @returns The _swapPropertiesmethod returns either thedestNodewith its key and value swapped with thesrcNode, or undefinedif eithersrcNodeordestNode` is falsy.

    Returns undefined | BinaryTreeNode<K, V>

[iterator]

  • [iterator](...args): IterableIterator<[K, undefined | V], any, any>

  • Time Complexity: O(n) Space Complexity: O(1)

    The function is an implementation of the Symbol.iterator method that returns an iterable iterator.

    Parameters

    • Rest...args: any[]

      The args parameter in the code snippet represents a rest parameter. It allows the function to accept any number of arguments as an array. In this case, the args parameter is used to pass any additional arguments to the _getIterator method.

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

add

  • add(keyNodeOrEntry, value?): boolean

  • Time Complexity: O(log n) Space Complexity: O(log n)

    The add function in TypeScript adds a new node to a binary search tree based on the key value.

    Parameters

    • keyNodeOrEntry:
          | undefined
          | null
          | K
          | BSTNode<K, V>
          | [undefined | null | K, undefined | V]

      The parameter keyNodeOrEntry can accept a value of type R or K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined .

    • Optionalvalue: V

      The value parameter is an optional value that can be associated with the key in the binary search tree. If provided, it will be stored in the node along with the key.

    Returns boolean

    a boolean value.

addMany

  • addMany(keysNodesEntriesOrRaws, values?, isBalanceAdd?, iterationType?): boolean[]

  • Time Complexity: O(k log n) Space Complexity: O(k + log n)

    The addMany function in TypeScript adds multiple keys or nodes to a data structure and returns an array indicating whether each key or node was successfully inserted.

    Parameters

    • keysNodesEntriesOrRaws: Iterable<R | BTNRep<K, V, BSTNode<K, V>>, any, any>

      An iterable containing keys, nodes, entries, or raw elements to be added to the data structure.

    • Optionalvalues: Iterable<undefined | V, any, any>

      An optional iterable of values to be associated with the keys or nodes being added. If provided, the values will be assigned to the corresponding keys or nodes in the same order. If not provided, undefined will be assigned as the value for each key or node.

    • OptionalisBalanceAdd: boolean = true

      A boolean flag indicating whether the tree should be balanced after adding the elements. If set to true, the tree will be balanced using a binary search tree algorithm. If set to false, the elements will be added without balancing the tree. The default value is true.

    • iterationType: IterationType = ...

      The iterationType parameter is an optional parameter that specifies the type of iteration to use when adding multiple keys or nodes to the binary search tree. It can have two possible values:

    Returns boolean[]

    The function addMany returns an array of booleans indicating whether each element was successfully inserted into the data structure.

bfs

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

  • Time complexity: O(n) Space complexity: O(n)

    The function overrides the breadth-first search method and returns an array of the return types of the callback function.

    Type Parameters

    Parameters

    • callback: C = ...

      The callback parameter is a function that will be called for each node visited during the breadth-first search. It should take a single argument, which is the current node being visited, and it can return a value of any type.

    • startNode:
          | undefined
          | null
          | K
          | BSTNode<K, V>
          | [undefined | null | K, undefined | V] = ...

      The startNode parameter is the starting point for the breadth-first search. It can be either a root node, a key-value pair, or an entry object. If no value is provided, the default value is the root of the tree.

    • iterationType: IterationType = ...

      The iterationType parameter is used to specify the type of iteration to be performed during the breadth-first search (BFS) traversal. It can have one of the following values:

    Returns ReturnType<C>[]

    an array of the return type of the callback function.

clear

clone

  • clone(): BST<K, V, R, MK, MV, MR>

  • Time complexity: O(n) Space complexity: O(n)

    The function clone overrides the default cloning behavior to create a deep copy of a tree structure.

    Returns BST<K, V, R, MK, MV, MR>

    The cloned object is being returned.

createNode

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

  • Time Complexity: O(1) Space Complexity: O(1)

    The function creates a new BSTNode with the given key and value and returns it.

    Parameters

    • key: K

      The key parameter is of type K, which represents the type of the key for the node being created.

    • Optionalvalue: V

      The "value" parameter is an optional parameter of type V. It represents the value associated with the key in the node being created.

    Returns BSTNode<K, V>

    The method is returning a new instance of the BSTNode class, casted as the BSTNode<K, V> type.

createTree

  • createTree(options?): BST<K, V, R, MK, MV, MR>

  • Time Complexity: O(1) Space Complexity: O(1)

    The function creates a new binary search tree with the specified options.

    Parameters

    • Optionaloptions: BSTOptions<K, V, R>

      The options parameter is an optional object that allows you to customize the behavior of the createTree method. It accepts a partial BSTOptions object, which has the following properties:

    Returns BST<K, V, R, MK, MV, MR>

    a new instance of the BST class with the provided options.

delete

  • delete(keyNodeOrEntry): BinaryTreeDeleteResult<BinaryTreeNode<K, V>>[]

  • Time Complexity: O(n) Space Complexity: O(1)

    The function delete in TypeScript implements the deletion of a node in a binary tree and returns the deleted node along with information for tree balancing.

    Parameters

    • keyNodeOrEntry:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]

      The delete method you provided is used to delete a node from a binary tree based on the key, node, entry or raw data. The method returns an array of BinaryTreeDeleteResult objects containing information about the deleted node and whether balancing is needed.

    Returns BinaryTreeDeleteResult<BinaryTreeNode<K, V>>[]

    The delete method returns an array of BinaryTreeDeleteResult objects. Each object in the array contains information about the node that was deleted (deleted) and the node that may need to be balanced (needBalanced).

dfs

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

  • Time complexity: O(n) Space complexity: O(n)

    The function dfs in TypeScript overrides the base class method with default parameters and returns the result of the super class dfs method.

    Type Parameters

    Parameters

    • callback: C = ...

      The callback parameter is a function that will be called for each node visited during the Depth-First Search traversal. It is a generic type C that extends the NodeCallback interface for BSTNode<K, V>. The default value for callback is this._ @param {DFSOrderPattern} [pattern=IN] - The patternparameter in theoverride dfsmethod specifies the order in which the Depth-First Search (DFS) traversal should be performed on the Binary Search Tree (BST). The possible values for thepatternparameter are: @param {boolean} [onlyOne=false] - TheonlyOneparameter in theoverride dfsmethod is a boolean flag that indicates whether you want to stop the depth-first search traversal after finding the first matching node or continue searching for all matching nodes. IfonlyOneis set totrue, the traversal will stop after finding @param {K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined} startNode - The startNodeparameter in theoverride dfsmethod can be one of the following types: @param {IterationType} iterationType - TheiterationTypeparameter in theoverride dfsmethod specifies the type of iteration to be performed during the Depth-First Search (DFS) traversal of a Binary Search Tree (BST). It is used to determine the order in which nodes are visited during the traversal. The possible values for

    • Optionalpattern: DFSOrderPattern = 'IN'
    • OptionalonlyOne: boolean = false
    • startNode:
          | undefined
          | null
          | K
          | BSTNode<K, V>
          | [undefined | null | K, undefined | V] = ...
    • iterationType: IterationType = ...

    Returns ReturnType<C>[]

    The override function is returning the result of calling the dfs method from the superclass, with the provided arguments callback, pattern, onlyOne, startNode, and iterationType. The return type is an array of the return type of the callback function C.

ensureNode

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

  • Time Complexity: O(log n) Space Complexity: O(log n)

    The function ensures the existence of a node in a data structure and returns it, or undefined if it doesn't exist.

    Parameters

    • keyNodeOrEntry:
          | undefined
          | null
          | K
          | BSTNode<K, V>
          | [undefined | null | K, undefined | V]

      The parameter keyNodeOrEntry can accept a value of type R, which represents the key, node, entry, or raw element that needs to be ensured in the tree.

    • OptionaliterationType: IterationType = ...

      The iterationType parameter is an optional parameter that specifies the type of iteration to be used when ensuring a node. It has a default value of 'ITERATIVE'.

    Returns OptNode<BSTNode<K, V>>

    The method is returning either the node that was ensured or undefined if the node could not be ensured.

entries

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

  • Time Complexity: O(n) Space Complexity: O(n)

    The function returns an iterator that yields key-value pairs from the object, where the value can be undefined.

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

every

  • every(predicate, thisArg?): boolean

  • Time Complexity: O(n) Space Complexity: O(1)

    The every function checks if every element in a collection satisfies a given condition.

    Parameters

    • predicate: EntryCallback<K, undefined | V, boolean>

      The predicate parameter is a callback function that takes three arguments: value, key, and index. It should return a boolean value indicating whether the condition is met for the current element in the iteration.

    • OptionalthisArg: any

      The thisArg parameter is an optional argument that specifies the value to be used as this when executing the predicate function. If thisArg is provided, it will be passed as the first argument to the predicate function. If thisArg is not provided

    Returns boolean

    The every method is returning a boolean value. It returns true if every element in the collection satisfies the provided predicate function, and false otherwise.

filter

  • filter(predicate, thisArg?): BinaryTree<K, V, R, MK, MV, MR>

  • Time Complexity: O(n) Space Complexity: O(n)

    The filter function iterates over key-value pairs in a tree data structure and creates a new tree with elements that satisfy a given predicate.

    Parameters

    • predicate: EntryCallback<K, undefined | V, boolean>

      The predicate parameter in the filter method is a function that will be called with four arguments: the value of the current entry, the key of the current entry, the index of the current entry in the iteration, and the reference to the tree itself (@param {any} [thisArg] - ThethisArgparameter in thefiltermethod allows you to specify the value ofthisthat should be used when executing thepredicatefunction. This is useful when thepredicatefunction relies on the context of a specific object or value. By providing athisArg

    • OptionalthisArg: any

    Returns BinaryTree<K, V, R, MK, MV, MR>

    The filter method is returning a new tree that contains entries that pass the provided predicate function.

find

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

  • Time Complexity: O(n) Space Complexity: O(1)

    The find function iterates over the entries of a collection and returns the first value for which the callback function returns true.

    Parameters

    • callbackfn: EntryCallback<K, undefined | V, boolean>

      The callback function that will be called for each entry in the collection. It takes three arguments: the value of the entry, the key of the entry, and the index of the entry in the collection. It should return a boolean value indicating whether the current entry matches the desired condition.

    • OptionalthisArg: any

      The thisArg parameter is an optional argument that specifies the value to be used as this when executing the callbackfn function. If thisArg is provided, it will be passed as the this value to the callbackfn function. If thisArg @returns The method findreturns the value of the first element in the iterable that satisfies the provided callback function. If no element satisfies the callback function,undefined` is returned.

    Returns undefined | [K, undefined | V]

forEach

  • forEach(callbackfn, thisArg?): void

  • Time Complexity: O(n) Space Complexity: O(1)

    The forEach function iterates over each key-value pair in a collection and executes a callback function for each pair.

    Parameters

    • callbackfn: EntryCallback<K, undefined | V, void>

      The callback function that will be called for each element in the collection. It takes four parameters: the value of the current element, the key of the current element, the index of the current element, and the collection itself.

    • OptionalthisArg: any

      The thisArg parameter is an optional argument that allows you to specify the value of this within the callback function. If thisArg is provided, it will be used as the this value when calling the callback function. If thisArg is not provided, `

    Returns void

get

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

  • Time Complexity: O(n) Space Complexity: O(log n)

    This function overrides the get method to retrieve the value associated with a specified key, node, entry, raw data, or predicate in a data structure.

    Parameters

    • keyNodeEntryOrPredicate:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]

      The keyNodeEntryOrPredicate parameter in the get method can accept one of the following types:

    • startNode:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V] = ...

      The startNode parameter in the get method is used to specify the starting point for searching for a key or node in the binary tree. If no specific starting point is provided, the default starting point is the root of the binary tree (this._root).

    • iterationType: IterationType = ...

      The iterationType parameter in the get method is used to specify the type of iteration to be performed when searching for a key in the binary tree. It is an optional parameter with a default value of this.iterationType, which means it will use the iteration type defined in the

    Returns undefined | V

    The get method is returning the value associated with the specified key, node, entry, raw data, or predicate in the binary tree map. If the specified key or node is found in the tree, the method returns the corresponding value. If the key or node is not found, it returns undefined.

getDepth

  • getDepth(dist, startNode?): number

  • Time Complexity: O(n) Space Complexity: O(log n)

    The getDepth function calculates the depth between two nodes in a binary tree.

    Parameters

    • dist:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]

      The dist parameter in the getDepth function represents the node or entry in a binary tree map, or a reference to a node in the tree. It is the target node for which you want to calculate the depth from the startNode node.

    • startNode:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V] = ...

      The startNode parameter in the getDepth function represents the starting point from which you want to calculate the depth of a given node or entry in a binary tree. If no specific starting point is provided, the default value for startNode is set to the root of the binary

    Returns number

    The getDepth method returns the depth of a given node dist relative to the startNode node in a binary tree. If the dist node is not found in the path to the startNode node, it returns the depth of the dist node from the root of the tree.

getHeight

  • getHeight(startNode?, iterationType?): number

  • Time Complexity: O(n) Space Complexity: O(log n)

    The getHeight function calculates the maximum height of a binary tree using either a recursive or iterative approach in TypeScript.

    Parameters

    • startNode:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V] = ...

      The startNode parameter is the starting point from which the height of the binary tree will be calculated. It can be a node in the binary tree or a reference to the root of the tree. If not provided, it defaults to the root of the binary tree data structure.

    • iterationType: IterationType = ...

      The iterationType parameter is used to determine the type of iteration to be performed while calculating the height of the binary tree. It can have two possible values:

    Returns number

    The getHeight method returns the height of the binary tree starting from the specified root node. The height is calculated based on the maximum depth of the tree, considering either a recursive approach or an iterative approach depending on the iterationType parameter.

getLeftMost

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

  • Time Complexity: O(log n) Space Complexity: O(log n)

    The function getLeftMost retrieves the leftmost node in a binary tree using either recursive or tail-recursive iteration.

    Type Parameters

    Parameters

    • callback: C = ...

      The callback parameter is a function that will be called with the leftmost node of a binary tree or with undefined if the tree is empty. It is provided with a default value of _DEFAULT_NODE_CALLBACK if not specified.

    • startNode:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V] = ...

      The startNode parameter in the getLeftMost function represents the starting point for finding the leftmost node in a binary tree. It can be either a key, a node, or an entry in the binary tree structure. If no specific starting point is provided, the function will default

    • iterationType: IterationType = ...

      The iterationType parameter in the getLeftMost function specifies the type of iteration to be used when traversing the binary tree nodes. It can have two possible values:

    Returns ReturnType<C>

    The getLeftMost function returns the result of the callback function C applied to the leftmost node in the binary tree starting from the startNode node. If the startNode node is NIL, it returns the result of the callback function applied to undefined. If the startNode node is not a real node, it returns the result of the callback

getMinHeight

  • getMinHeight(startNode?, iterationType?): number

  • Time Complexity: O(n) Space Complexity: O(log n)

    The getMinHeight function calculates the minimum height of a binary tree using either a recursive or iterative approach in TypeScript.

    Parameters

    • startNode:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V] = ...

      The startNode parameter in the getMinHeight function represents the starting node from which the minimum height of the binary tree will be calculated. It is either a node in the binary tree or a reference to the root of the tree. If not provided, the default value is the root

    • iterationType: IterationType = ...

      The iterationType parameter in the getMinHeight method specifies the type of iteration to use when calculating the minimum height of a binary tree. It can have two possible values:

    Returns number

    The getMinHeight method returns the minimum height of the binary tree starting from the specified root node. The height is calculated based on the shortest path from the root node to a leaf node in the tree. The method uses either a recursive approach or an iterative approach (using a stack) based on the iterationType parameter.

getNode

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

  • Time Complexity: O(log n) Space Complexity: O(log n)

    This function retrieves a node based on a given keyNodeEntryOrPredicate within a binary search tree structure.

    Parameters

    • keyNodeEntryOrPredicate:
          | undefined
          | null
          | K
          | BSTNode<K, V>
          | [undefined | null | K, undefined | V]
          | NodePredicate<BSTNode<K, V>>

      The keyNodeEntryOrPredicate parameter can be of type K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined , R, or NodePredicate<BSTNode<K, V>>.

    • startNode: BSTNOptKeyOrNode<K, BSTNode<K, V>> = ...

      The startNode parameter in the getNode method is used to specify the starting point for searching nodes in the binary search tree. If no specific starting point is provided, the default value is set to this._root, which is the root node of the binary search tree.

    • iterationType: IterationType = ...

      The iterationType parameter in the getNode method is a parameter that specifies the type of iteration to be used. It has a default value of this.iterationType, which means it will use the iteration type defined in the class instance if no value is provided when calling the method.

    Returns OptNode<BSTNode<K, V>>

    The getNode method is returning an optional binary search tree node (OptNode<BSTNode<K, V>>). It is using the getNodes method to find the node based on the provided keyNodeEntryOrPredicate, beginning at the specified root node (startNode) and using the specified iteration type. The method then returns the first node found or undefined if no node is found.

getNodes

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

  • Parameters

    • keyNodeEntryOrPredicate:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]
          | NodePredicate<BinaryTreeNode<K, V>>

      The getNodes function you provided takes several parameters:

    • OptionalonlyOne: boolean

      The onlyOne parameter in the getNodes function is a boolean flag that determines whether to return only the first node that matches the criteria specified by the keyNodeEntryOrPredicate parameter. If onlyOne is set to true, the function will

    • OptionalstartNode:
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]

      The startNode parameter in the getNodes function is used to specify the starting point for traversing the binary tree. It represents the root node of the binary tree or the node from which the traversal should begin. If not provided, the default value is set to this._root @param {IterationType} iterationType - The iterationTypeparameter in thegetNodesfunction determines the type of iteration to be performed when traversing the nodes of a binary tree. It can have two possible values: @returns ThegetNodes` function returns an array of nodes that satisfy the provided condition based on the input parameters and the iteration type specified.

    • OptionaliterationType: IterationType

    Returns BinaryTreeNode<K, V>[]

getPathToRoot

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

  • Time Complexity: O(log n) Space Complexity: O(log n)

    The function getPathToRoot in TypeScript retrieves the path from a given node to the root of a tree structure, applying a specified callback function along the way.

    Type Parameters

    Parameters

    • beginNode:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]
    • callback: C = ...

      The callback parameter is a function that is used to process each node in the path to the root. It is expected to be a function that takes a node as an argument and returns a value based on that node. The return type of the callback function is determined by the generic type C @param {K | BinaryTreeNode<K, V> | [K | null | undefined, V | undefined] | null | undefined } beginNode - The beginNodeparameter in thegetPathToRootfunction can be either a key, a node, an entry, or any other value of typeR. @param [isReverse=true] - The isReverseparameter in thegetPathToRootfunction determines whether the resulting path from the givenbeginNodeto the root should be in reverse order or not. IfisReverseis set totrue, the path will be reversed before being returned. If is

    • OptionalisReverse: boolean = false

    Returns ReturnType<C>[]

    The function getPathToRoot returns an array of the return values of the callback function callback applied to each node in the path from the beginNode to the root node. The array is either in reverse order or in the original order based on the value of the isReverse parameter.

getPredecessor

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

  • Time Complexity: O(log n) Space Complexity: O(log n)

    The function getPredecessor in TypeScript returns the predecessor node of a given node in a binary tree.

    Parameters

    • node: BinaryTreeNode<K, V>

      The getPredecessor function you provided seems to be attempting to find the predecessor of a given node in a binary tree. However, there seems to be a logical issue in the while loop condition that might cause an infinite loop.

    Returns BinaryTreeNode<K, V>

    The getPredecessor function returns the predecessor node of the input BinaryTreeNode<K, V> parameter. If the left child of the input node exists, it traverses to the rightmost node of the left subtree to find the predecessor. If the left child does not exist, it returns the input node itself.

getRightMost

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

  • Time Complexity: O(log n) Space Complexity: O(log n)

    The function getRightMost retrieves the rightmost node in a binary tree using either recursive or iterative traversal methods.

    Type Parameters

    Parameters

    • callback: C = ...

      The callback parameter is a function that will be called with the result of finding the rightmost node in a binary tree. It is of type NodeCallback<OptNodeOrNull<BinaryTreeNode<K, V>>>, which means it is a callback function that can accept either an optional binary tree node or null as

    • startNode:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V] = ...

      The startNode parameter in the getRightMost function represents the starting point for finding the rightmost node in a binary tree. It can be either a key, a node, or an entry in the binary tree structure. If no specific starting point is provided, the function will default

    • iterationType: IterationType = ...

      The iterationType parameter in the getRightMost function specifies the type of iteration to be used when traversing the binary tree nodes. It can have two possible values:

    Returns ReturnType<C>

    The getRightMost function returns the result of the callback function C, which is passed as a parameter to the function. The callback function is called with the rightmost node in the binary tree structure, determined based on the specified iteration type ('RECURSIVE' or other).

getSuccessor

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

  • Time Complexity: O(log n) Space Complexity: O(log n)

    The function getSuccessor in TypeScript returns the next node in an in-order traversal of a binary tree.

    Parameters

    • Optionalx: null | K | BinaryTreeNode<K, V>

      The getSuccessor function takes a parameter x, which can be of type K, BinaryTreeNode<K, V>, or null.

    Returns undefined | null | BinaryTreeNode<K, V>

    The getSuccessor function returns the successor node of the input node x. If x has a right child, the function returns the leftmost node in the right subtree of x. If x does not have a right child, the function traverses up the parent nodes until it finds a node that is not the right child of its parent, and returns that node

has

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

  • Time Complexity: O(n) Space Complexity: O(1)

    The function checks if a given key exists in a collection.

    Parameters

    • OptionalkeyNodeEntryOrPredicate:
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]
          | NodePredicate<BinaryTreeNode<K, V>>
    • OptionalstartNode:
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]
    • OptionaliterationType: IterationType

    Returns boolean

    a boolean value. It returns true if the key is found in the collection, and false otherwise.

hasValue

  • hasValue(value): boolean

  • Time Complexity: O(n) Space Complexity: O(1)

    The function checks if a given value exists in a collection.

    Parameters

    • value: undefined | V

      The parameter "value" is the value that we want to check if it exists in the collection.

    Returns boolean

    a boolean value, either true or false.

isAVLBalanced

  • isAVLBalanced(iterationType?): boolean

  • Time Complexity: O(n) Space Complexity: O(log n)

    The function isAVLBalanced checks if a binary tree is AVL balanced using either a recursive or iterative approach.

    Parameters

    • iterationType: IterationType = ...

      The iterationType parameter is an optional parameter that specifies the type of iteration to use when checking if the AVL tree is balanced. It has a default value of this.iterationType, which means it will use the iteration type specified in the current instance of the AVL tree.

    Returns boolean

    a boolean value.

isBST

  • isBST(startNode?, iterationType?): boolean

  • Time Complexity: O(n) Space Complexity: O(log n)

    The function isBST in TypeScript checks if a binary search tree is valid using either recursive or iterative methods.

    Parameters

    • startNode:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V] = ...

      The startNode parameter in the isBST function represents the starting point for checking whether a binary search tree (BST) is valid. It can be a node in the BST or a reference to the root of the BST. If no specific node is provided, the function will default to

    • iterationType: IterationType = ...

      The iterationType parameter in the isBST function determines whether the function should use a recursive approach or an iterative approach to check if the binary search tree (BST) is valid.

    Returns boolean

    The isBST method is returning a boolean value, which indicates whether the binary search tree (BST) represented by the given root node is a valid BST or not. The method checks if the tree satisfies the BST property, where for every node, all nodes in its left subtree have keys less than the node's key, and all nodes in its right subtree have keys greater than the node's

isEmpty

  • isEmpty(): boolean

  • Time Complexity: O(1) Space Complexity: O(1)

    The isEmpty function in TypeScript checks if a data structure has no elements and returns a boolean value.

    Returns boolean

    The isEmpty() method is returning a boolean value, specifically true if the _size property is equal to 0, indicating that the data structure is empty, and false otherwise.

isEntry

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

  • Time Complexity: O(1) Space Complexity: O(1)

    The function isEntry checks if the input is a BTNEntry object by verifying if it is an array with a length of 2.

    Parameters

    • keyNodeOrEntry:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]

      The keyNodeOrEntry parameter in the isEntry function can be of type K | BinaryTreeNode<K, V> | [K | null | undefined, V | undefined] | null | undefined or type R. The function checks if the provided keyNodeOrEntry is of type BTN @returns The isEntryfunction is checking if thekeyNodeOrEntryparameter is an array with a length of 2. If it is, then it returnstrue, indicating that the parameter is of type BTNEntry<K, V>. If the condition is not met, it returns false`.

    Returns keyNodeOrEntry is BTNEntry<K, V>

isLeaf

  • isLeaf(keyNodeOrEntry): boolean

  • Time Complexity: O(1) Space Complexity: O(1)

    The function determines whether a given key, node, entry, or raw data is a leaf node in a binary tree.

    Parameters

    • keyNodeOrEntry:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]

      The parameter keyNodeOrEntry can be of type K | BinaryTreeNode<K, V> | [K | null | undefined, V | undefined] | null | undefined or R. It represents a key, node, entry, or raw data in a binary tree structure. The function isLeaf checks whether the provided

    Returns boolean

    The function isLeaf returns a boolean value indicating whether the input keyNodeOrEntry is a leaf node in a binary tree.

isNIL

  • isNIL(keyNodeOrEntry): boolean

  • Time Complexity: O(1) Space Complexity: O(1)

    The function isNIL checks if a given key, node, entry, or raw value is equal to the _NIL value.

    Parameters

    • keyNodeOrEntry:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]

      BTNRep<K, V, BinaryTreeNode<K, V>>

    Returns boolean

    The function is checking if the keyNodeOrEntry parameter is equal to the _NIL property of the current object and returning a boolean value based on that comparison.

isNode

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

  • Time Complexity: O(1) Space Complexity: O(1)

    The function checks if the input is an instance of the BSTNode class.

    Parameters

    • keyNodeOrEntry:
          | undefined
          | null
          | K
          | BSTNode<K, V>
          | [undefined | null | K, undefined | V]

      The parameter keyNodeOrEntry can be of type R or K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined .

    Returns keyNodeOrEntry is BSTNode<K, V>

    a boolean value indicating whether the input parameter keyNodeOrEntry is an instance of the BSTNode class.

isPerfectlyBalanced

  • isPerfectlyBalanced(startNode?): boolean

  • Time Complexity: O(n) Space Complexity: O(log n)

    The function checks if a binary tree is perfectly balanced by comparing its minimum height with its height.

    Parameters

    • startNode:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V] = ...

      The startNode parameter is the starting point for checking if the binary tree is perfectly balanced. It represents the root node of the binary tree or a specific node from which the balance check should begin.

    Returns boolean

    The method isPerfectlyBalanced is returning a boolean value, which indicates whether the tree starting from the startNode node is perfectly balanced or not. The return value is determined by comparing the minimum height of the tree with the height of the tree. If the minimum height plus 1 is greater than or equal to the height of the tree, then it is considered perfectly balanced and

isRange

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

  • Time Complexity: O(1) Space Complexity: O(1)

    The function isRange checks if the input parameter is an instance of the Range class.

    Parameters

    • keyNodeEntryOrPredicate:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]
          | Range<K>
          | NodePredicate<BinaryTreeNode<K, V>>

      The keyNodeEntryOrPredicate parameter in the isRange function can be of type K | BinaryTreeNode<K, V> | [K | null | undefined, V | undefined] | null | undefined , NodePredicate<BinaryTreeNode<K, V>>, or Range<K>. The function checks if the keyNodeEntry @returns The isRangefunction is checking if thekeyNodeEntryOrPredicateparameter is an instance of theRangeclass. If it is an instance ofRange, the function will return true, indicating that the parameter is a Range. If it is not an instance of Range, the function will return false`.

    Returns keyNodeEntryOrPredicate is Range<K>

isRaw

  • isRaw(keyNodeEntryOrRaw): keyNodeEntryOrRaw is R

  • Time Complexity: O(1) Space Complexity: O(1)

    The function isRaw checks if the input parameter is of type R by verifying if it is an object.

    Parameters

    • keyNodeEntryOrRaw:
          | undefined
          | null
          | K
          | R
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]

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

    Returns keyNodeEntryOrRaw is R

    The function isRaw is checking if the keyNodeEntryOrRaw parameter is of type R by checking if it is an object. If the parameter is an object, the function will return true, indicating that it is of type R.

isRealNode

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

  • Time Complexity: O(1) Space Complexity: O(1)

    The function isRealNode checks if a given input is a valid node in a binary tree.

    Parameters

    • keyNodeOrEntry:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]

      The keyNodeOrEntry parameter in the isRealNode function can be of type K | BinaryTreeNode<K, V> | [K | null | undefined, V | undefined] | null | undefined or R. The function checks if the input parameter is a BinaryTreeNode<K, V> type by verifying if it is not equal

    Returns keyNodeOrEntry is BinaryTreeNode<K, V>

    The function isRealNode is checking if the input keyNodeOrEntry is a valid node by comparing it to this._NIL, null, and undefined. If the input is not one of these values, it then calls the isNode method to further determine if the input is a node. The function will return a boolean value indicating whether the

isRealNodeOrNull

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

  • Time Complexity: O(1) Space Complexity: O(1)

    The function checks if a given input is a valid node or null.

    Parameters

    • keyNodeOrEntry:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]

      The parameter keyNodeOrEntry in the isRealNodeOrNull function can be of type BTNRep<K, V, BinaryTreeNode<K, V>> or R. It is a union type that can either be a key, a node, an entry, or

    Returns keyNodeOrEntry is null | BinaryTreeNode<K, V>

    The function isRealNodeOrNull is returning a boolean value. It checks if the input keyNodeOrEntry is either null or a real node, and returns true if it is a node or null, and false otherwise.

isValidKey

  • isValidKey(key): key is K

  • Time Complexity: O(1) Space Complexity: O(1)

    The function "override isValidKey" checks if a key is comparable based on a given comparator.

    Parameters

    • key: any

      The key parameter is a value that will be checked to determine if it is of type K.

    Returns key is K

    The override isValidKey(key: any): key is K function is returning a boolean value based on the result of the isComparable function with the condition this._compare !== this._DEFAULT_COMPARATOR.

keys

  • keys(): IterableIterator<K, any, any>

  • Time Complexity: O(n) Space Complexity: O(n)

    The function returns an iterator that yields the keys of a data structure.

    Returns IterableIterator<K, any, any>

leaves

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

  • Time complexity: O(n) Space complexity: O(n)

    The leaves function in TypeScript returns an array of values from leaf nodes in a binary tree structure based on a specified callback and iteration type.

    Type Parameters

    Parameters

    • callback: C = ...

      The callback parameter is a function that will be called on each leaf node in the binary tree. It is optional and defaults to a default callback function if not provided.

    • startNode:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V] = ...

      The startNode parameter in the leaves method is used to specify the starting point for finding and processing the leaves of a binary tree. It can be provided as either a key, a node, or an entry in the binary tree structure. If not explicitly provided, the default value

    • iterationType: IterationType = ...

      The iterationType parameter in the leaves method specifies the type of iteration to be performed when collecting the leaves of a binary tree. It can have two possible values:

    Returns ReturnType<C>[]

    The leaves method returns an array of values that are the result of applying the provided callback function to each leaf node in the binary tree.

lesserOrGreaterTraverse

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

  • Time complexity: O(n) Space complexity: O(n)

    The lesserOrGreaterTraverse function traverses a binary tree and applies a callback function to each node that meets a certain condition based on a target node and a comparison value.

    Type Parameters

    Parameters

    • callback: C = ...

      The callback parameter is a function that will be called for each node that meets the condition specified by the lesserOrGreater parameter. It takes a single argument, which is the current node being traversed, and returns a value of any type.

    • lesserOrGreater: CP = -1

      The lesserOrGreater parameter is used to determine whether to traverse nodes that are lesser, greater, or both than the targetNode. It accepts the values -1, 0, or 1, where:

    • targetNode:
          | undefined
          | null
          | K
          | BSTNode<K, V>
          | [undefined | null | K, undefined | V] = ...

      The targetNode parameter is the node in the binary tree that you want to start traversing from. It can be specified either by providing the key of the node, the node itself, or an entry containing the key and value of the node. If no targetNode is provided,

    • iterationType: IterationType = ...

      The iterationType parameter determines the type of traversal to be performed on the binary tree. It can have two possible values:

    Returns ReturnType<C>[]

    The function lesserOrGreaterTraverse returns an array of values of type ReturnType<C>, which is the return type of the callback function passed as an argument.

listLevels

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

  • Time complexity: O(n) Space complexity: O(n)

    The function overrides the listLevels method from the superclass and returns an array of arrays containing the results of the callback function applied to each level of the tree.

    Type Parameters

    Parameters

    • callback: C = ...

      The callback parameter is a generic type C that extends NodeCallback<BSTNode<K, V> | null>. It represents a callback function that will be called for each node in the tree during the iteration process.

    • startNode:
          | undefined
          | null
          | K
          | BSTNode<K, V>
          | [undefined | null | K, undefined | V] = ...

      The startNode parameter is the starting point for listing the levels of the binary tree. It can be either a root node of the tree, a key-value pair representing a node in the tree, or a key representing a node in the tree. If no value is provided, the root of

    • iterationType: IterationType = ...

      The iterationType parameter is used to specify the type of iteration to be performed on the tree. It can have one of the following values:

    Returns ReturnType<C>[][]

    The method is returning a two-dimensional array of the return type of the callback function.

map

  • map(callback, options?, thisArg?): BST<MK, MV, MR, any, any, object>

  • Time complexity: O(n) Space complexity: O(n)

    The map function in TypeScript overrides the default map behavior for a binary search tree by applying a callback function to each entry and creating a new tree with the results.

    Parameters

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

      A function that will be called for each entry in the BST. It takes four arguments: the key, the value (which can be undefined), the index of the entry, and a reference to the BST itself.

    • Optionaloptions: BSTOptions<MK, MV, MR>

      The options parameter in the override map method is of type BSTOptions<MK, MV, MR>. It is an optional parameter that allows you to specify additional options for the Binary Search Tree (BST) being created in the map method. These options could include configuration

    • OptionalthisArg: any

      The thisArg parameter in the override map method is used to specify the value of this that should be used when executing the callback function. It allows you to set the context or scope in which the callback function will be called. This can be useful when you want

    Returns BST<MK, MV, MR, any, any, object>

    The map method is returning a new Binary Search Tree (BST) instance with the entries transformed by the provided callback function.

merge

  • merge(anotherTree): void

  • Time Complexity: O(k * n) Space Complexity: O(1)

    The merge function in TypeScript merges another binary tree into the current tree by adding all elements from the other tree.

    Parameters

    Returns void

morris

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

  • Type Parameters

    Parameters

    • Optionalcallback: C

      The callback parameter in the morris function is a function that will be called on each node in the binary tree during the traversal. It is of type C, which extends the NodeCallback<BinaryTreeNode<K, V> | null> type. The default value for callback is this._DEFAULT @param {DFSOrderPattern} [pattern=IN] - The patternparameter in themorrisfunction specifies the type of Depth-First Search (DFS) order pattern to traverse the binary tree. The possible values for thepatternparameter are: @param {K | BinaryTreeNode<K, V> | [K | null | undefined, V | undefined] | null | undefined } startNode - ThestartNodeparameter in themorrisfunction is the starting point for the Morris traversal algorithm. It represents the root node of the binary tree or the node from which the traversal should begin. It can be provided as either a key, a node, an entry, or a reference @returns Themorris` function is returning an array of values that are the result of applying the provided callback function to each node in the binary tree in the specified order pattern (IN, PRE, or POST).

    • Optionalpattern: DFSOrderPattern
    • OptionalstartNode:
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V]

    Returns ReturnType<C>[]

perfectlyBalance

  • perfectlyBalance(iterationType?): boolean

  • Time complexity: O(n) Space complexity: O(n)

    The perfectlyBalance function takes an optional iterationType parameter and returns true if the binary search tree is perfectly balanced, otherwise it returns false.

    Parameters

    • iterationType: IterationType = ...

      The iterationType parameter is an optional parameter that specifies the type of iteration to use when building a balanced binary search tree. It has a default value of this.iterationType, which means it will use the iteration type specified in the current instance of the class.

    Returns boolean

    The function perfectlyBalance returns a boolean value.

print

  • print(options?, startNode?): void

  • Time Complexity: O(n) Space Complexity: O(n)

    The function print in TypeScript overrides the default print behavior to log a visual representation of the binary tree to the console.

    Parameters

    • Optionaloptions: BinaryTreePrintOptions

      The options parameter is used to specify the printing options for the binary tree. It is an optional parameter that allows you to customize how the binary tree is printed, such as choosing between different traversal orders or formatting options.

    • startNode:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V] = ...

      The startNode parameter in the override print method is used to specify the starting point for printing the binary tree. It can be either a key, a node, an entry, or the root of the tree. If no specific starting point is provided, the default value is set to

    Returns void

rangeSearch

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

  • Time Complexity: O(log n) Space Complexity: O(k + log n)

    The rangeSearch function searches for nodes within a specified range in a binary search tree.

    Type Parameters

    Parameters

    • range: Range<K> | [K, K]

      The range parameter in the rangeSearch function can be either a Range object or an array of two elements representing the range boundaries.

    • callback: C = ...

      The callback parameter in the rangeSearch function is a callback function that is used to process each node that is found within the specified range during the search operation. It is of type NodeCallback<BSTNode<K, V> | null>, where BSTNode<K, V> is the type of nodes in the data structure.

    • startNode:
          | undefined
          | null
          | K
          | BSTNode<K, V>
          | [undefined | null | K, undefined | V] = ...

      The startNode parameter in the rangeSearch function represents the node from which the search for nodes within the specified range will begin. It is the starting point for the range search operation.

    • iterationType: IterationType = ...

      The iterationType parameter in the rangeSearch function is used to specify the type of iteration to be performed during the search operation. It has a default value of this.iterationType, which suggests that it is likely a property of the class or object that the rangeSearch

    Returns ReturnType<C>[]

    The rangeSearch function is returning the result of calling the search method with the specified parameters.

reduce

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

  • Time Complexity: O(n) Space Complexity: O(1)

    The reduce function iterates over key-value pairs and applies a callback function to each pair, accumulating a single value.

    Type Parameters

    • U

    Parameters

    • callbackfn: ReduceEntryCallback<K, undefined | V, U>

      The callback function that will be called for each element in the collection. It takes four arguments: the current accumulator value, the current value of the element, the key of the element, and the index of the element in the collection. It should return the updated accumulator value.

    • initialValue: U

      The initialValue parameter is the initial value of the accumulator. It is the value that will be used as the first argument to the callbackfn function when reducing the elements of the collection.

    Returns U

    The reduce method is returning the final value of the accumulator after iterating over all the elements in the collection.

refill

  • refill(keysNodesEntriesOrRaws, values?): void

  • Time Complexity: O(k * n) Space Complexity: O(1)

    The refill function clears the existing data structure and then adds new key-value pairs based on the provided input.

    Parameters

    • keysNodesEntriesOrRaws: Iterable<
          | undefined
          | null
          | K
          | R
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V], any, any>

      The keysNodesEntriesOrRaws parameter in the refill method can accept an iterable containing a mix of K | BinaryTreeNode<K, V> | [K | null | undefined, V | undefined] | null | undefined objects or R objects.

    • Optionalvalues: Iterable<undefined | V, any, any>

      The values parameter in the refill method is an optional parameter that accepts an iterable of values of type V or undefined.

    Returns void

search

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

  • Time Complexity: O(log n) Space Complexity: O(k + log n)

    The function search in TypeScript overrides the search behavior in a binary tree structure based on specified criteria.

    Type Parameters

    Parameters

    • keyNodeEntryOrPredicate:
          | undefined
          | null
          | K
          | BSTNode<K, V>
          | [undefined | null | K, undefined | V]
          | NodePredicate<BSTNode<K, V>>
          | Range<K>

      The keyNodeEntryOrPredicate parameter in the override search method can accept one of the following types:

    • OptionalonlyOne: boolean = false

      The onlyOne parameter is a boolean flag that determines whether the search should stop after finding the first matching node. If onlyOne is set to true, the search will return as soon as a matching node is found. If onlyOne is set to false, the

    • callback: C = ...

      The callback parameter in the override search function is a function that will be called on each node that matches the search criteria. It is of type C, which extends NodeCallback<BSTNode<K, V> | null>. The callback function should accept a node of type BSTNode<K, V> as its argument and

    • startNode:
          | undefined
          | null
          | K
          | BSTNode<K, V>
          | [undefined | null | K, undefined | V] = ...

      The startNode parameter in the override search method represents the node from which the search operation will begin. It is the starting point for searching within the tree data structure. The method ensures that the startNode is a valid node before proceeding with the search operation. If the @param {IterationType} iterationType - TheiterationTypeparameter in theoverride searchfunction determines the type of iteration to be used during the search operation. It can have two possible values: @returns Theoverride search` method returns an array of values that match the search criteria specified by the input parameters. The method performs a search operation on a binary tree structure based on the provided key, predicate, and other options. The search results are collected in an array and returned as the output of the method.

    • iterationType: IterationType = ...

    Returns ReturnType<C>[]

some

  • some(predicate, thisArg?): boolean

  • Time Complexity: O(n) Space Complexity: O(1)

    The "some" function iterates over a collection and returns true if at least one element satisfies a given predicate.

    Parameters

    • predicate: EntryCallback<K, undefined | V, boolean>

      The predicate parameter is a callback function that takes three arguments: value, key, and index. It should return a boolean value indicating whether the condition is met for the current element in the iteration.

    • OptionalthisArg: any

      The thisArg parameter is an optional argument that specifies the value to be used as the this value when executing the predicate function. If thisArg is provided, it will be passed as the first argument to the predicate function. If thisArg is

    Returns boolean

    a boolean value. It returns true if the predicate function returns true for any pair in the collection, and false otherwise.

toVisual

  • toVisual(startNode?, options?): string

  • Time Complexity: O(n) Space Complexity: O(n)

    The function toVisual in TypeScript overrides the visual representation of a binary tree with customizable options for displaying undefined, null, and sentinel nodes.

    Parameters

    • startNode:
          | undefined
          | null
          | K
          | BinaryTreeNode<K, V>
          | [undefined | null | K, undefined | V] = ...

      The startNode parameter in the toVisual method is used to specify the starting point for visualizing the binary tree structure. It can be a node, key, entry, or the root of the tree. If no specific starting point is provided, the default is set to the root

    • Optionaloptions: BinaryTreePrintOptions

      The options parameter in the toVisual method is an object that contains the following properties:

    Returns string

    The override toVisual method returns a string that represents the visual display of the binary tree based on the provided options for showing undefined, null, and Red-Black NIL nodes. The method constructs the visual representation by calling the _displayAux method and appending the lines to the output string. The final output string contains the visual representation of the binary tree with the specified options.

values

  • values(): IterableIterator<undefined | V, any, any>

  • Time Complexity: O(n) Space Complexity: O(n)

    The function returns an iterator that yields the values of a collection.

    Returns IterableIterator<undefined | V, any, any>

Settings

Member Visibility

On This Page

Constructors
Methods