This is the constructor function for a Red-Black Tree data structure in TypeScript.
The keysNodesEntriesOrRaws parameter is an
iterable object that can contain either keys, nodes, entries, or raw elements. It is used to
initialize the RBTree with the provided elements.
Optionaloptions: RBTreeOptions<K, V, R>The options parameter is an optional object that can be passed to the
constructor. It is of type RBTreeOptions<K, V, R>. This object can contain various options for
configuring the behavior of the Red-Black Tree. The specific properties and their meanings would
depend on the implementation
Protected_clearProtected_clearProtected_deleteTime Complexity: O(log n) Space Complexity: O(1)
The _deleteFixup function is used to fix the red-black tree after a node deletion by adjusting
the colors and performing rotations.
The node parameter represents a node in a binary tree. It can
be either a valid node object or undefined.
The function does not return any value. It has a return type of void, which means it
does not return anything.
Protected_dfsTime complexity: O(n) Space complexity: O(n)
The _dfs function performs a depth-first search traversal on a binary tree structure based on
the specified order pattern and callback function.
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 of type C, which
extends NodeCallback<OptNodeOrNull<NODE>>. The default value for this parameter is this._DEFAULT @param {DFSOrderPattern} [pattern=IN] - The patternparameter in the_dfsmethod specifies the order in which the nodes are visited during the Depth-First Search traversal. It can have one of the following values: @param {BTNRep<K, V, NODE> | R} startNode - ThestartNodeparameter in the_dfsmethod is used to specify the starting point for the depth-first search traversal in a binary tree. It can be provided as either aBTNRepobject or a reference to the root node of the tree. If no specific @param {IterationType} iterationType - TheiterationTypeparameter in the_dfsmethod specifies the type of iteration to be performed during the Depth-First Search (DFS) traversal of a binary tree. It can have two possible values: @param [includeNull=false] - TheincludeNullparameter in the_dfsmethod is a boolean flag that determines whether null nodes should be included in the depth-first search traversal. IfincludeNullis set totrue, null nodes will be considered during the traversal process. If it is set to false, @param shouldVisitLeft - The shouldVisitLeftparameter is a function that takes a node as input and returns a boolean value. It is used to determine whether the left child of a node should be visited during the depth-first search traversal. By default, it checks if the node is truthy (not null or undefined @param shouldVisitRight - TheshouldVisitRightparameter is a function that takes a node as an argument and returns a boolean value. It is used to determine whether the right child of a node should be visited during the depth-first search traversal. The default implementation checks if the node is truthy before visiting the right child @param shouldVisitRoot - TheshouldVisitRootparameter is a function that takes a node as an argument and returns a boolean value. It is used to determine whether the root node should be visited during the depth-first search traversal based on certain conditions. The default implementation checks if the node is a real node or null based @param shouldProcessRoot - TheshouldProcessRootparameter is a function that takes a node as an argument and returns a boolean value indicating whether the node should be processed during the depth-first search traversal. The default implementation checks if the node is a real node or null based on theincludeNullflag. If
Optionalpattern: DFSOrderPattern = 'IN'OptionalincludeNull: boolean = falseThe function _dfs returns an array of the return type of the callback function provided
as input.
Protected_displayTime 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.
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
The options parameter in the _displayAux function
contains the following properties:
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_ensureTime Complexity: O(1) Space Complexity: O(1)
The function _ensurePredicate in TypeScript ensures that the input is converted into a valid
predicate function for a binary tree node.
The
_ensurePredicate method in the provided code snippet is responsible for ensuring that the input
parameter keyNodeEntryRawOrPredicate is transformed into a valid predicate function that can be
used for filtering nodes in a binary tree.
A NodePredicate
Protected_getTime 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.
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
Protected_getTime Complexity: O(1) Space Complexity: O(1)
The function _getKey in TypeScript returns the key from a given input, which can be a node,
entry, raw data, or null/undefined.
The _getKey method you provided is a
TypeScript method that takes in a parameter keyNodeEntryOrRaw of type BTNRep<K, V, NODE> | R,
where BTNRep is a generic type with keys K, V, and NODE, and @returns The_getKeymethod returns the key value extracted from thekeyNodeEntryOrRawparameter. The return value can be a key value of typeK, null, or undefined`, depending on
the conditions checked in the method.
Protected_insertTime Complexity: O(log n) Space Complexity: O(1)
The _insert function inserts a node into a binary search tree and performs necessary fix-ups to
maintain the red-black tree properties.
The node parameter represents the node that needs to be inserted into the
binary search tree.
a string value indicating the result of the insertion operation. It can return either 'UPDATED' if the node with the same key already exists and was updated, or 'CREATED' if a new node was created and inserted into the tree.
Protected_insertTime Complexity: O(log n) Space Complexity: O(1)
The _insertFixup function is used to fix the Red-Black Tree after inserting a new node.
The parameter z represents a node in the Red-Black Tree data
structure. It can either be a valid node or undefined.
Protected_isTime Complexity: O(1) Space Complexity: O(1)
The function _isPredicate checks if a given parameter is a function.
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<NODE>.
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_leftTime Complexity: O(1) Space Complexity: O(1)
The _leftRotate function performs a left rotation on a given node in a binary tree.
The parameter x is of type NODE | undefined. It represents a
node in a binary tree or undefined if there is no node.
void, which means it does not return any value.
Protected_replaceTime Complexity: O(1) Space Complexity: O(1)
The function replaces an old node with a new node while preserving the color of the old node.
The method is returning the result of calling the _replaceNode method from the
superclass, with the oldNode and newNode parameters.
Protected_rightTime Complexity: O(1) Space Complexity: O(1)
The _rightRotate function performs a right rotation on a given node in a binary tree.
The parameter y is of type NODE | undefined. It represents a
node in a binary tree or undefined if there is no node.
void, which means it does not return any value.
Protected_setTime 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.
v is a parameter of type NODE or undefined.
Protected_setTime 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.
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_swapTime Complexity: O(1) Space Complexity: O(1)
The _swapProperties function swaps key and value properties between two nodes in a binary tree.
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.
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 BTNRep<K, V, NODE> 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.
Protected_transplantTime Complexity: O(n) Space Complexity: O(1)
The function is an implementation of the Symbol.iterator method that returns an iterable iterator.
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.
Time Complexity: O(log n) Space Complexity: O(1)
The function adds a new node to a binary search tree and returns true if the node was successfully added.
The parameter
keyNodeEntryOrRaw can accept a value of type R or BTNRep<K, V, NODE>.
Optionalvalue: VThe value parameter is an optional value that you want to associate with
the key in the data structure. It represents the value that you want to add or update in the data
structure.
The method is returning a boolean value. If a new node is successfully added to the tree, the method returns true. If the node already exists and its value is updated, the method also returns true. If the node cannot be added or updated, the method returns false.
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.
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 = trueA 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.
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:
The function addMany returns an array of booleans indicating whether each element was
successfully inserted into the data structure.
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.
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.
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.
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:
an array of the return type of the callback function.
Time complexity: O(n) Space complexity: O(n)
The clone function creates a deep copy of a tree structure by traversing it using breadth-first
search.
The clone() method is returning a cloned copy of the tree with the same structure and
values as the original tree. The method creates a new tree, iterates over the nodes of the
original tree using breadth-first search (bfs), and adds the nodes to the new tree. If a node in
the original tree is null, a null node is added to the cloned tree. If a node
The function creates a new Red-Black Tree node with the specified key, value, and color.
The key parameter represents the key value of the node being created. It is of type K, which is a generic type that can be replaced with any specific type when using the function.
Optionalvalue: VThe value parameter is an optional parameter that represents the value
associated with the key in the node. It is not required and can be omitted if you only need to
create a node with a key.
Optionalcolor: RBTNColor = 'BLACK'The "color" parameter is used to specify the color of the node in a Red-Black Tree. It can have two possible values: "RED" or "BLACK". By default, the color is set to "BLACK" if not specified.
A new instance of a RedBlackTreeNode with the specified key, value, and color is being returned.
Time Complexity: O(log n) Space Complexity: O(1)
The function overrides the delete method in a binary tree data structure to remove a node based on a given predicate and maintain the binary search tree properties.
The keyNodeEntryOrRaw
parameter in the override delete method is used to specify the condition or key based on which a
node should be deleted from the binary tree. It can be a key, a node, an entry, or a predicate
function that determines which node(s) should be deleted.
The override delete method is returning an array of BinaryTreeDeleteResult<NODE>
objects. Each object in the array contains information about the deleted node and whether
balancing is needed.
Time complexity: O(n) Space complexity: O(n)
The function overrides the depth-first search method and returns an array of the return types of the callback function.
The callback parameter is a function that will be called for each node
during the depth-first search traversal. It is an optional parameter and defaults to
this._DEFAULT_NODE_CALLBACK. The type C represents the type of the callback function.
Optionalpattern: DFSOrderPattern = 'IN'The "pattern" parameter in the code snippet refers to the order in which the Depth-First Search (DFS) algorithm visits the nodes in a tree or graph. It can take one of the following values:
The startNode parameter is the starting
point for the depth-first search traversal. It can be either a root node, a key-value pair, or a
node entry. If not specified, the default value is the root of the tree.
OptionaliterationType: IterationType = ...The iterationType parameter specifies the
type of iteration to be used during the Depth-First Search (DFS) traversal. It can have one of the
following values:
The method is returning an array of the return type of the callback function.
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.
The parameter
keyNodeEntryOrRaw 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'.
The method is returning either the node that was ensured or undefined if the node could
not be ensured.
Time Complexity: O(n) Space Complexity: O(1)
The every function checks if every element in a collection satisfies a given condition.
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: anyThe 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
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.
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.
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: anyThe filter method is returning a new tree that contains entries that pass the provided
predicate function.
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.
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: anyThe 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.
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.
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: anyThe 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, `
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.
The keyNodeEntryRawOrPredicate parameter in the get method can accept one of the
following types:
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).
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
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.
Time Complexity: O(n) Space Complexity: O(1)
The getDepth function calculates the depth between two nodes in a binary tree.
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.
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
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.
Time Complexity: O(n) Space Complexity: O(1)
The getHeight function calculates the maximum height of a binary tree using either a recursive
or iterative approach in TypeScript.
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.
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:
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.
Time Complexity: O(log n) Space Complexity: O(1)
The function getLeftMost retrieves the leftmost node in a binary tree using either recursive or
tail-recursive iteration.
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.
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
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:
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
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.
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
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:
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.
Time Complexity: O(log n) Space Complexity: O(1)
This function retrieves a node based on a given keyNodeEntryRawOrPredicate within a binary search tree structure.
The keyNodeEntryRawOrPredicate
parameter can be of type BTNRep<K, V, NODE>, R, or NodePredicate<NODE>.
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.
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.
The getNode method is returning an optional binary search tree node (OptNode<NODE>).
It is using the getNodes method to find the node based on the provided keyNodeEntryRawOrPredicate, 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.
Time Complexity: O(log n) Space Complexity: O(1)
The function getNodeByKey returns a node with a specific key from a tree data structure.
The key parameter is the value used to search for a specific node in the tree. It is typically a unique identifier or a value that can be used to determine the position of the node in the tree structure.
OptionaliterationType: IterationType = ...The iterationType parameter is an optional
parameter that specifies the type of iteration to be used when searching for a node in the tree.
It has a default value of 'ITERATIVE'.
The method is returning a NODE object or undefined.
Time Complexity: O(log n) Space Complexity: O(k + log n)
The function getNodes in TypeScript overrides the base class method to retrieve nodes based on a
given keyNodeEntryRawOrPredicate and iteration type.
The keyNodeEntryRawOrPredicate
parameter in the getNodes method is used to filter the nodes that will be returned. It can be a
key, a node, an entry, or a custom keyNodeEntryRawOrPredicate function that determines whether a node should be
included in the result.
OptionalonlyOne: boolean = falseThe onlyOne parameter in the getNodes method is a boolean flag that
determines whether to return only the first node that matches the keyNodeEntryRawOrPredicate (true) or all nodes
that match the keyNodeEntryRawOrPredicate (false). If onlyOne is set to true, the method will stop iterating
and
The startNode parameter in the
getNodes method is used to specify the starting point for traversing the tree when searching for
nodes that match a given keyNodeEntryRawOrPredicate. It represents the root node of the subtree where the search
should begin. If not explicitly provided, the default value for begin @param {IterationType} iterationType - The iterationTypeparameter in thegetNodesmethod specifies the type of iteration to be performed when traversing the nodes of a binary tree. It can have two possible values: @returns ThegetNodes` method returns an array of nodes that satisfy the given keyNodeEntryRawOrPredicate.
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.
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 {BTNRep<K, V, NODE> | R} 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 = trueThe 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.
Time Complexity: O(log n) Space Complexity: O(1)
The function getPredecessor in TypeScript returns the predecessor node of a given node in a
binary tree.
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.
The getPredecessor function returns the predecessor node of the input NODE 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.
Time Complexity: O(log n) Space Complexity: O(1)
The function getRightMost retrieves the rightmost node in a binary tree using either recursive
or iterative traversal methods.
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<NODE>>,
which means it is a callback function that can accept either an optional binary tree node or null
as
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
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:
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).
Time Complexity: O(log n) Space Complexity: O(1)
The function getSuccessor in TypeScript returns the next node in an in-order traversal of a
binary tree.
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
Time Complexity: O(n) Space Complexity: O(log n)
The has function in TypeScript checks if a specified key, node, entry, raw data, or predicate
exists in the data structure.
The keyNodeEntryRawOrPredicate parameter in the override has method can accept one of
the following types:
The startNode parameter in the
override method is used to specify the starting point for the search operation within the data
structure. It defaults to this._root if not provided explicitly.
The iterationType parameter in the override has method
is used to specify the type of iteration to be performed. It has a default value of
this.iterationType, which means it will use the iteration type defined in the current context if
no value is provided when calling the method.
The override has method is returning a boolean value. It checks if there are any nodes
that match the provided key, node, entry, raw data, or predicate in the tree structure. If there
are matching nodes, it returns true, indicating that the tree contains the specified element.
Otherwise, it returns false.
Time Complexity: O(n) Space Complexity: O(1)
The function checks if a given value exists in a collection.
The parameter "value" is the value that we want to check if it exists in the collection.
a boolean value, either true or false.
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.
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.
a boolean value.
Time Complexity: O(n) Space Complexity: O(1)
The function isBST in TypeScript checks if a binary search tree is valid using either recursive
or iterative methods.
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
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.
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
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.
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.
The function isEntry checks if the input is a BTNEntry object by verifying if it is an array
with a length of 2.
The keyNodeEntryOrRaw
parameter in the isEntry function can be of type BTNRep<K, V, NODE> or type R.
The function checks if the provided keyNodeEntryOrRaw is of type BTN @returns The isEntryfunction is checking if thekeyNodeEntryOrRawparameter 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`.
The function "override isKey" checks if a key is comparable based on a given comparator.
The key parameter is a value that will be checked to determine if it is of
type K.
The override isKey(key: any): key is K function is returning a boolean value based on
the result of the isComparable function with the condition this.comparator !== this._DEFAULT_COMPARATOR.
The function isNIL checks if a given key, node, entry, or raw value is equal to the _NIL value.
The function is checking if the keyNodeEntryOrRaw parameter is equal to the _NIL
property of the current object and returning a boolean value based on that comparison.
Time Complexity: O(1) Space Complexity: O(1)
The function checks if the input is an instance of the RedBlackTreeNode class.
a boolean value indicating whether the input parameter keyNodeEntryOrRaw is
an instance of the RedBlackTreeNode class.
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.
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
The function isRealNode checks if a given input is a valid node in a binary tree.
The function isRealNode is checking if the input keyNodeEntryOrRaw 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
The function checks if a given input is a valid node or null.
The function isRealNodeOrNull is returning a boolean value. It checks if the input
keyNodeEntryOrRaw is either null or a real node, and returns true if it is a node or
null, and false otherwise.
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.
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.
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
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:
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.
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.
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.
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:
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,
The iterationType parameter determines the type of
traversal to be performed on the binary tree. It can have two possible values:
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.
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.
The callback parameter is a generic type C that extends
NodeCallback<NODE>. It represents a callback function that will be called for each node in the
tree during the iteration process.
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
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:
The method is returning a two-dimensional array of the return type of the callback function.
Time Complexity: O(n) Space Complexity: O(n)
The map function iterates over key-value pairs in a tree data structure, applies a callback
function to each value, and returns a new tree with the updated values.
The callback parameter in the map method is a function that will be called
on each entry in the tree. It takes four arguments:
OptionalthisArg: anyThe thisArg parameter in the map function is an optional parameter
that specifies the value to be passed as this when executing the callback function. If provided,
the thisArg value will be used as the this value within the callback function. If thisArg @returns The map` method is returning a new tree with the entries modified by the provided
callback function. Each entry in the original tree is passed to the callback function, and the
result of the callback function is added to the new tree.
Time complexity: O(n) Space complexity: O(n)
The morris function in TypeScript performs a Depth-First Search traversal on a binary tree using
Morris Traversal algorithm with different order patterns.
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<NODE> 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 {BTNRep<K, V, NODE> | R} 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 = 'IN'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.
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.
The function perfectlyBalance returns a boolean value.
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.
Optionaloptions: BinaryTreePrintOptionsThe 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.
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
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.
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.
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.
The reduce method is returning the final value of the accumulator after iterating over
all the elements in the collection.
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.
The keysNodesEntriesOrRaws parameter in the refill
method can accept an iterable containing a mix of BTNRep<K, V, NODE> 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.
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.
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: anyThe 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
a boolean value. It returns true if the predicate function returns true for any pair in the collection, and false otherwise.
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.
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: BinaryTreePrintOptionsThe options parameter in the toVisual method is an
object that contains the following properties:
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.