/** * Represents a node in a linked list. * @template V - Type of the value held by the node. * @template N - Type of the reference to the next node. */ declare abstract class LLNode { abstract val: V; abstract next: N | null; } /** * Represents a base linked list. * @template V - Type of the value held by the list. * @template N - Type of the reference to the nodes in the list. */ declare abstract class BaseLinkedList { protected _head: N | null; protected _tail: N | null; protected _length: number; protected constructor(); /** * Get the reference to the head node of the list. * @returns {N | null} - Reference to the head node. */ get head(): N | null; /** * Get the reference to the tail node of the list. * @returns {N | null} - Reference to the tail node. */ get tail(): N | null; /** * Get the size of the list. * @returns {number} - The size of the list. */ get size(): number; /** * Check if the list is empty. * @returns {boolean} - Indicates whether the list is empty or not. */ get isEmpty(): boolean; /** * Add a new node with the provided value to the end of the list. * @param {V} val - Value to be added to the list. * @returns {BaseLinkedList} - Updated list. */ abstract push(val: V): BaseLinkedList; /** * Remove and return the value from the end of the list. * @returns {V | undefined} - Removed value. */ abstract pop(): V | undefined; /** * Remove and return the value from the beginning of the list. * @returns {V | undefined} - Removed value. */ abstract shift(): V | undefined; /** * Add a new node with the provided value to the beginning of the list. * @param {V} val - Value to be added to the beginning of the list. * @returns {BaseLinkedList} - Updated list. */ abstract unshift(val: V): BaseLinkedList; /** * Get the value at the specified index. * @param {number} index - Index of the value to retrieve. * @returns {V | undefined} - Retrieved value. */ abstract at(index: number): V | undefined; /** * Get the node at the specified index. * @param {number} index - Index of the node to retrieve. * @returns {N | null} - Retrieved node. */ abstract nodeAt(index: number): N | null; /** * Set the value at the specified index. * @param {number} index - Index where the value needs to be set. * @param {V} val - Value to be set. * @returns {boolean} - Indicates if the value was successfully set or not. */ abstract setAt(index: number, val: V): boolean; /** * Insert a value at the specified index. * @param {number} index - Index where the value needs to be inserted. * @param {V} val - Value to be inserted. * @returns {boolean} - Indicates if the value was successfully inserted or not. */ abstract insertAt(index: number, val: V): boolean; /** * Delete the value at the specified index. * @param {number} index - Index where the value needs to be deleted. * @returns {V | undefined} - Deleted value. */ abstract deleteAt(index: number): V | undefined; /** * Reverse the order of the nodes in the list. * @returns {BaseLinkedList} - Reversed list. */ abstract reverse(): BaseLinkedList; /** * Clears the linked list by resetting its properties. * @returns {void} * @timecomplexity O(1) - Constant time as it directly resets the properties. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ clear(): void; /** * Checks if the provided index is a valid index within the list. * @param {number} index - Index to be checked. * @returns {boolean} - Indicates if the index is valid. */ protected isValidIndex(index: number): boolean; } /** * Represents a node in a singly linked list. * @template T - Type of the value held by the node. */ declare class SLLNode extends LLNode> { val: T; next: SLLNode; constructor(val: T); } /** * Represents a singly linked list. * @template T - Type of the value held by the list. */ declare class SinglyLinkedList extends BaseLinkedList> { constructor(); /** * Create a singly linked list from an array. * @param {T[]} data - Array to create the list from. * @returns {SinglyLinkedList} - Singly linked list created from the array. * @timecomplexity O(n) - Where 'n' is the length of the input array. * @spacecomplexity O(n) - Additional space used is linearly proportional to the length of the input array. */ static fromArray(data: T[]): SinglyLinkedList; /** * Adds a new node with the provided value to the end of the list. * @param {T} val - Value to be added to the list. * @returns {SinglyLinkedList} - Updated list. * @timecomplexity O(1) - Constant time complexity as it only adds to the end of the list. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ push(val: T): SinglyLinkedList; /** * Removes and returns the value from the end of the list. * @returns {T | undefined} - Removed value. * @timecomplexity O(n) - Linear time as it may traverse the list to find the last element. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ pop(): T | undefined; /** * Removes and returns the value from the beginning of the list. * @returns {T | undefined} - Removed value. * @timecomplexity O(1) - Constant time complexity as it only removes from the beginning of the list. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ shift(): T | undefined; /** * Adds a new node with the provided value to the beginning of the list. * @param {T} val - Value to be added to the beginning of the list. * @returns {SinglyLinkedList} - Updated list. * @timecomplexity O(1) - Constant time complexity as it only adds to the beginning of the list. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ unshift(val: T): SinglyLinkedList; /** * Get the value at the specified index. * @param {number} index - Index of the value to retrieve. * @returns {T | undefined} - Retrieved value. * @timecomplexity O(n) - Linear time as it may traverse the list to find the node at the specified index. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ at(index: number): T | undefined; /** * Get the node at the specified index. * @param {number} index - Index of the node to retrieve. * @returns {SLLNode | null} - Retrieved node or null if index is invalid. * @timecomplexity O(n) - Linear time as it may traverse the list to find the node at the specified index. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ nodeAt(index: number): SLLNode | null; /** * Set the value at the specified index. * @param {number} index - Index where the value needs to be set. * @param {T} val - Value to be set. * @returns {boolean} - Indicates if the value was successfully set or not. * @timecomplexity O(n) - Linear time as it may traverse the list to find the node at the specified index. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ setAt(index: number, val: T): boolean; /** * Insert a value at the specified index. * @param {number} index - Index where the value needs to be inserted. * @param {T} val - Value to be inserted. * @returns {boolean} - Indicates if the value was successfully inserted or not. * @timecomplexity O(n) - Linear time as it may traverse the list to find the node before the specified index. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ insertAt(index: number, val: T): boolean; /** * Delete the value at the specified index. * @param {number} index - Index where the value needs to be deleted. * @returns {T | undefined} - Deleted value or undefined if index is invalid. * @timecomplexity O(n) - Linear time as it may traverse the list to find the node before the specified index. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ deleteAt(index: number): T | undefined; /** * Reverse the order of the nodes in the list. * @returns {SinglyLinkedList} - The reversed list. * @timecomplexity O(n) - Linear time as it traverses through the entire list to reverse it. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ reverse(): SinglyLinkedList; /** * Rotate the list by the specified number of positions. * @param {number} n - Number of positions to rotate the list. * @returns {SinglyLinkedList} - The rotated list. * @timecomplexity O(n) - Linear time as it may traverse through the list to perform rotations. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ rotateByN(n: number): SinglyLinkedList; /** * Convert the list to an array. * @returns {T[]} - An array containing the elements of the list in order. * @timecomplexity O(n) - Linear time as it traverses through the entire list to build the array. * @spacecomplexity O(n) - Additional space used is linearly proportional to the list's length. */ toArray(): T[]; } /** * Represents a node in a doubly linked list. * @template T - Type of the value held by the node. */ declare class DLLNode extends LLNode> { val: T; prev: DLLNode | null; next: DLLNode | null; constructor(val: T); } /** * Represents a doubly linked list. * @template T - Type of the value held by the list. */ declare class DoublyLinkedList extends BaseLinkedList> { constructor(); /** * Creates a doubly linked list from an array. * @param {T[]} data - Array to create the list from. * @returns {DoublyLinkedList} - Doubly linked list created from the array. * @timecomplexity O(n) - Linear time as it iterates through each element in the input array to create the list. * @spacecomplexity O(n) - Additional space used is directly proportional to the number of elements in the input array and the resulting list. */ static fromArray(data: T[]): DoublyLinkedList; /** * Adds a new node with the provided value to the end of the list. * @param {T} val - Value to be added to the list. * @returns {DoublyLinkedList} - Updated list. * @timecomplexity O(1) - Constant time as it adds an element at the end of the list. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ push(val: T): DoublyLinkedList; /** * Removes and returns the value from the end of the list. * @returns {T | undefined} - Removed value or undefined if the list is empty. * @timecomplexity O(1) - Constant time as it removes an element from the end of the list. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ pop(): T | undefined; /** * Removes and returns the value from the beginning of the list. * @returns {T | undefined} - Removed value or undefined if the list is empty. * @timecomplexity O(1) - Constant time as it removes an element from the beginning of the list. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ shift(): T | undefined; /** * Adds a new node with the provided value to the beginning of the list. * @param {T} val - Value to be added to the beginning of the list. * @returns {DoublyLinkedList} - Updated list. * @timecomplexity O(1) - Constant time as it adds an element at the beginning of the list. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ unshift(val: T): DoublyLinkedList; /** * Returns the value at the specified index in the list. * @param {number} index - Index to retrieve the value from. * @returns {T | undefined} - Value at the index or undefined if the index is out of range. * @timecomplexity O(n) - Linear time in the worst case, as it traverses the list to reach the desired index. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ at(index: number): T | undefined; /** * Retrieves the node at the specified index in the list. * @param {number} index - Index to retrieve the node from. * @returns {DLLNode | null} - Node at the index or null if the index is out of range. * @timecomplexity O(n) - Linear time in the worst case, as it traverses the list to reach the desired index. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ nodeAt(index: number): DLLNode | null; /** * Sets the value at the specified index in the list. * @param {number} index - Index where the value should be set. * @param {T} val - Value to set at the index. * @returns {boolean} - True if the value is successfully set, false if the index is out of range. * @timecomplexity O(n) - Linear time in the worst case, as it traverses the list to reach the desired index. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ setAt(index: number, val: T): boolean; /** * Inserts a new node with the provided value at the specified index in the list. * @param {number} index - Index where the value should be inserted. * @param {T} val - Value to insert at the index. * @returns {boolean} - True if the value is successfully inserted, false if the index is out of range. * @timecomplexity O(n) - Linear time in the worst case, as it might traverse the list to reach the desired index. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ insertAt(index: number, val: T): boolean; /** * Deletes the node at the specified index in the list. * @param {number} index - Index of the node to be deleted. * @returns {T | undefined} - Value of the deleted node or undefined if the index is out of range. * @timecomplexity O(n) - Linear time in the worst case, as it might traverse the list to reach the desired index. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ deleteAt(index: number): T | undefined; /** * Reverses the order of nodes in the list. * @returns {DoublyLinkedList} - The reversed list. * @timecomplexity O(n) - Linear time, as it traverses the list to reverse the order of nodes. * @spacecomplexity O(1) - Constant space is used regardless of the list size. */ reverse(): DoublyLinkedList; /** * Converts the list into an array of its values. * @returns {T[]} - Array containing the values of the list. * @timecomplexity O(n) - Linear time, as it traverses the list to create the array of values. * @spacecomplexity O(n) - Additional space is directly proportional to the number of elements in the list. */ toArray(): T[]; } /** * Queue class represents a basic queue data structure that follows the First-In-First-Out (FIFO) principle. * It uses a singly linked list internally for efficient enqueue and dequeue operations. * @template T - The type of elements stored in the queue. */ declare class Queue { list: SinglyLinkedList; /** * Creates an instance of the Queue class. * The underlying data structure is a singly linked list. */ constructor(); /** * Retrieves the value at the front of the queue. * @returns {T | undefined} The value at the front of the queue, or undefined if the queue is empty. * @timecomplexity O(1) - Constant time complexity as accessing the head of a linked list is a constant time operation. * @spacecomplexity O(1) - Constant space complexity as no additional data structures are used. */ get front(): T | undefined; /** * Retrieves the value at the rear of the queue. * @returns {T | undefined} The value at the rear of the queue, or undefined if the queue is empty. * @timecomplexity O(1) - Constant time complexity as accessing the tail of a linked list is a constant time operation. * @spacecomplexity O(1) - Constant space complexity as no additional data structures are used. */ get rear(): T | undefined; /** * Returns the number of elements in the queue. * @returns {number} - The size of the queue. * @timecomplexity O(1) * @spacecomplexity O(1) */ get size(): number; /** * Checks if the queue is empty. * @returns {boolean} - True if the queue is empty, false otherwise. * @timecomplexity O(1) * @spacecomplexity O(1) */ get isEmpty(): boolean; /** * Adds an element to the rear of the queue and returns the new size of the queue. * @param {T} val - The value to enqueue. * @returns {number} - The updated size of the queue. * @timecomplexity O(1) * @spacecomplexity O(1) */ enqueue(val: T): number; /** * Removes and returns the element from the front of the queue. * @returns {T | undefined} - The value dequeued from the front of the queue. * @timecomplexity O(1) * @spacecomplexity O(1) */ dequeue(): T | undefined; /** * Retrieves the value at the front of the queue without removing it. * @returns {T | undefined} - The value at the front of the queue. * @timecomplexity O(1) * @spacecomplexity O(1) */ peek(): T | undefined; /** * Retrieves the value at the rear of the queue without removing it. * @returns {T | undefined} - The value at the rear of the queue. * @timecomplexity O(1) * @spacecomplexity O(1) */ peekRear(): T | undefined; /** * Removes all elements from the queue * @timecomplexity O(1) * @spacecomplexity O(1) */ clear(): void; /** * Returns an array representation of the queue. * @returns {T[]} - An array containing all elements in the queue. * @timecomplexity O(n) * @spacecomplexity O(n) */ toArray(): T[]; } /** * Represents a stack data structure that follows the Last-In-First-Out (LIFO) principle. * It uses a singly linked list internally for efficient push and pop operations. * @template T - The type of elements in the stack. */ declare class Stack { private list; /** * Creates a new instance of the Stack class. * The underlying data structure is a singly linked list. */ constructor(); /** * Retrieves the value at the top of the stack. * @returns {T | undefined} The value at the front of the queue, or undefined if the queue is empty. * @timecomplexity O(1) - Constant time complexity as accessing the head of a linked list is a constant time operation. * @spacecomplexity O(1) - Constant space complexity as no additional data structures are used. */ get top(): T | undefined; /** * Returns the number of elements in the stack. * @returns {number} - The size of the stack. * @timecomplexity O(1) * @spacecomplexity O(1) */ get size(): number; /** * Checks if the stack is empty. * @returns {boolean} - True if the stack is empty, false otherwise. * @timecomplexity O(1) * @spacecomplexity O(1) */ get isEmpty(): boolean; /** * Adds a new element to the top of the stack. * @param {T} val - The value to be pushed onto the stack. * @timecomplexity O(1) * @spacecomplexity O(1) */ push(val: T): void; /** * Removes and returns the element from the top of the stack. * @returns {T | undefined} The value popped from the stack, or undefined if the stack is empty. * @timecomplexity O(1) * @spacecomplexity O(1) */ pop(): T | undefined; /** * Retrieves the value at the top of the stack without removing it. * @returns {T | undefined} The value at the top of the stack, or undefined if the stack is empty. * @timecomplexity O(1) * @spacecomplexity O(1) */ peek(): T | undefined; /** * Removes all elements from the stack. * @timecomplexity O(1) * @spacecomplexity O(1) */ clear(): void; /** * Returns an array representation of the stack. * @returns {T[]} An array containing the elements of the stack in top-to-bottom order. * @timecomplexity O(n) * @spacecomplexity O(n) */ toArray(): T[]; } declare enum TraversalOrder { PreOrder = 0, InOrder = 1, PostOrder = 2, LevelOrder = 3 } /** * Represents a node in a binary tree. * @template K - The type of the key (number or string). * @template V - The type of the value stored in the node. */ declare class BTNode { key: K; val: V; left: BTNode | null; right: BTNode | null; /** * Creates a new instance of the BTNode class. * @param {K} key - The key associated with the node. * @param {V} val - The value associated with the node. */ constructor(key: K, val: V); } type Key = number | string; type Entries = [K, V][]; type TraversalFn = (val: V, key: K, node: BTNode) => void; type MatchFn = (val: V, key: K, node: BTNode) => boolean; type BSTComparator = (a: K, b: K) => number; /** * Represents an abstract base class for a binary tree structure with generic data. * @template K - The type of the keys (number or string) stored in the binary tree nodes. * @template V - The type of the value stored in the binary tree nodes. */ declare abstract class BinaryTreeBase { protected _root: BTNode | null; protected _size: number; protected constructor(); /** * Gets the root node of the binary tree. * @returns {BTNode | null} - The root node of the binary tree. */ get root(): BTNode | null; /** * Gets the number of nodes in the binary tree. * @returns {number} - The size of the binary tree. */ get size(): number; /** * Checks if the binary tree is empty. * @returns {boolean} - `true` if the binary tree is empty, `false` otherwise. */ get isEmpty(): boolean; abstract get(key: K, order?: TraversalOrder): V | undefined; abstract has(key: K, order?: TraversalOrder): boolean; abstract set(key: K, val: V, order?: TraversalOrder): boolean; abstract node(key: K): BTNode | null; abstract add(key: K, val: V): void; abstract delete(key: K): void; /** * Iterates over each node in the binary tree, in a specified order and applies a callback function. * @param {TraversalFn} traversalFn - The callback function to apply to each node. * @param {TraversalOrder} [order] - The order of traversal (default: InOrder). * @returns {void} * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity * - O(h) for depth-first traversals, where h is the height of the binary tree. * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree. */ forEach(traversalFn: TraversalFn, order?: TraversalOrder): void; /** * Finds a node in the binary tree that matches a given condition using the specified traversal order. * @param {MatchFn} matchFn - The condition to match nodes. * @param {TraversalOrder} [order] - The order of traversal (default: InOrder). * @returns {BTNode | null} - The first node that matches the condition, or `null` if not found. * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity * - O(h) for depth-first traversals, where h is the height of the binary tree. * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree. */ findNode(matchFn: MatchFn, order?: TraversalOrder): BTNode | null; /** * Finds the value in the binary tree that matches a given condition using the specified traversal order. * @param {MatchFn} matchFn - The condition to match values. * @param {TraversalOrder} [order] - The order of traversal (default: InOrder). * @returns {V | undefined} - The first value that matches the condition, or `undefined` if not found. * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity * - O(h) for depth-first traversals, where h is the height of the binary tree. * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree. */ findValue(matchFn: MatchFn, order?: TraversalOrder): V | undefined; /** * Checks if any node in the binary tree matches a given condition using the specified traversal order. * @param {MatchFn} matchFn - The condition to match nodes. * @param {TraversalOrder} [order] - The order of traversal (default: InOrder). * @returns {boolean} - `true` if at least one node matches the condition, `false` otherwise. * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity * - O(h) for depth-first traversals, where h is the height of the binary tree. * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree. */ some(matchFn: MatchFn, order?: TraversalOrder): boolean; /** * Checks if all nodes in the binary tree match a given condition using the specified traversal order. * @param {MatchFn} matchFn - The condition to match nodes. * @param {TraversalOrder} [order] - The order of traversal (default: InOrder). * @returns {boolean} - `true` if all nodes match the condition, `false` otherwise. * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity * - O(h) for depth-first traversals, where h is the height of the binary tree. * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree. */ every(matchFn: MatchFn, order?: TraversalOrder): boolean; /** * Clears the binary tree, removing all nodes. * @returns {void} * * @timecomplexity O(1) * @spacecomplexity O(1) */ clear(): void; /** * Gets the maximum depth of the binary tree. * @returns {number} - The maximum depth of the binary tree. * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity O(h), where h is the height of the binary tree. */ maxDepth(): number; /** * Checks if the binary tree is equal to another tree by comparing their structures. * @param {BTNode | null} root - The root of the other binary tree. * @returns {boolean} - `true` if the binary trees are equal, * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity O(h), where h is the height of the binary tree. */ isEqual(root: BTNode | null): boolean; /** * Checks if the binary tree is perfect. * A binary tree is considered perfect if all nodes have exactly two children, and all leaf nodes are at the same level. * @returns {boolean} True if the tree is perfect, false otherwise. * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity O(h), where h is the height of the binary tree. */ isPerfect(): boolean; /** * Checks if the binary tree is full. * A binary tree is considered full if each node has either 0 or 2 children. * @returns {boolean} - True if the binary tree is full, false otherwise. * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity O(h), where h is the height of the binary tree. */ isFull(): boolean; /** * Checks if the binary tree is complete. * A binary tree is considered complete if all levels, except possibly the last, * are completely filled, and all nodes are as left as possible. * @returns {boolean} - True if the binary tree is complete, false otherwise. * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity O(w), where w is the maximum width of the binary tree. */ isComplete(): boolean; /** * Checks if the binary tree is balanced. * A binary tree is considered balanced if the height of the two subtrees of any node * never differs by more than one. * @returns {boolean} - True if the binary tree is balanced, false otherwise. * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity O(h), where h is the height of the binary tree. */ isBalanced(): boolean; /** * Generates an iterator for the keys in the binary tree using the specified traversal order. * @param {TraversalOrder} [order] - The order of traversal (default: InOrder). * @returns {Generator} - An iterator for the keys in the binary tree. * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity * - O(h) for depth-first traversals, where h is the height of the binary tree. * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree. */ keys(order?: TraversalOrder): Generator; /** * Generates an iterator for the values in the binary tree using the specified traversal order. * @param {TraversalOrder} [order] - The order of traversal (default: InOrder). * @returns {Generator} - An iterator for the values in the binary tree. * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity * - O(h) for depth-first traversals, where h is the height of the binary tree. * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree. */ values(order?: TraversalOrder): Generator; /** * Generates an iterator for the entries (key-value pairs) in the binary tree using the specified traversal order. * @param {TraversalOrder} [order] - The order of traversal (default: InOrder). * @returns {Generator<[K, V], void, void>} - An iterator for the entries in the binary tree. * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity * - O(h) for depth-first traversals, where h is the height of the binary tree. * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree. */ entries(order?: TraversalOrder): Generator<[K, V], void, void>; /** * Generates an iterator for the nodes in the binary tree using the specified traversal order. * @param {TraversalOrder} [order] - The order of traversal (default: InOrder). * @returns {Generator, void, void>} - An iterator for the nodes in the binary tree. * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity * - O(h) for depth-first traversals, where h is the height of the binary tree. * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree. */ nodes(order?: TraversalOrder): Generator, void, void>; protected setRoot(root: BTNode | null): void; protected setSize(number: number): void; } /** * Represents a binary tree. * * @extends {BinaryTreeBase} * @template K - The type of the keys (number or string) stored in the binary tree nodes. * @template V - The type of the value stored in the binary tree nodes. */ declare class BinaryTree extends BinaryTreeBase { /** * Constructs a new instance of the BinaryTree class. * @param {BTNode | null} [root] - The root node of the binary tree. * If not provided, the tree will be initialized as empty. * @param {number} [size] - The size of the binary tree. * If not provided, the size will be calculated based on the root node. */ constructor(root?: BTNode | null, size?: number); /** * Creates a new BinaryTree instance from an array of entries using level-order (BFS) traversal for insertion. * @template K - The type of the key (number or string). * @template V - The type of the value stored in the node. * @param {Entries} entries - The entries to initialize the binary tree. * @returns {BinaryTree} - A new binary tree instance. * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity O(w), where w is the maximum width of the binary tree. */ static fromEntries(entries: Entries): BinaryTree; /** * Gets the value associated with the specified key in the binary tree, employing the chosen traversal order. * @param {number | string} key - The key to search for. * @param {TraversalOrder} [order] - The order of traversal (default: InOrder). * @returns {V | undefined} - The value associated with the key, or undefined if not found. * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity * - O(h) for depth-first traversals, where h is the height of the binary tree. * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree. */ get(key: K, order?: TraversalOrder): V | undefined; /** * Gets the node with the specified key in the binary tree, employing the chosen traversal order. * @param {K} key - The key to search for. * @param {TraversalOrder} [order] - The order of traversal (default: InOrder). * @returns {BTNode} - The node with the specified key. * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity * - O(h) for depth-first traversals, where h is the height of the binary tree. * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree. */ node(key: K, order?: TraversalOrder): BTNode; /** * Checks if the binary tree contains a node with the specified key, employing the chosen traversal order. * @param {K} key - The key to check for. * @param {TraversalOrder} [order] - The order of traversal (default: InOrder). * @returns {boolean} - True if the binary tree contains a node with the specified key, false otherwise. * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity * - O(h) for depth-first traversals, where h is the height of the binary tree. * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree. */ has(key: K, order?: TraversalOrder): boolean; /** * Sets the value associated with the specified key in the binary tree, employing the chosen traversal order. * @param {K} key - The key to set. * @param {V} val - The value to associate with the key. * @param {TraversalOrder} [order] - The order of traversal (default: InOrder). * @returns {boolean} - True if the key was successfully set, false otherwise. * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity * - O(h) for depth-first traversals, where h is the height of the binary tree. * - O(w) for breadth-first traversal, where w is the maximum width of the binary tree. */ set(key: K, val: V, order?: TraversalOrder): boolean; /** * Adds a new node with the given key and value to the binary tree, employing level-order (BFS) traversal for insertion. * @param {K} key - The key of the new node. * @param {V} val - The value of the new node. * @returns {void} * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity O(w), where w is the maximum width of the binary tree. */ add(key: K, val: V): void; /** * Adds multiple nodes with the given keys and values to the binary tree, employing level-order (BFS) traversal for insertion. * @param {Entries} entries - An array of key-value pairs to be added to the binary tree. * @returns {void} * * @timecomplexity O(n), where n is the total number of nodes (both existing nodes in the tree and the nodes to be added). * @spacecomplexity O(w), where w is the maximum width of the binary tree. */ addMany(entries: Entries): void; /** * Deletes the node with the specified key from the binary tree. * It replaces the node with the deepest rightmost node and then removes the deepest rightmost node. * @param {K} key - The key of the node to be deleted. * @returns {boolean} - `true` if the node with the given key was found and deleted, `false` otherwise. * * @timecomplexity O(n), where n is the number of nodes in the binary tree. * @spacecomplexity O(w), where w is the maximum width of the binary tree. */ delete(key: K): boolean; } /** * Represents a binary search tree. * @template K - The type of the keys (number or string) stored in the binary tree nodes. * @template V - The type of the value stored in the binary tree nodes. */ declare class BinarySearchTree extends BinaryTreeBase { private readonly comparator; /** * Constructor for BinarySearchTree. * @param {BSTComparator} [comparator] - The comparator function for keys of the binary search tree. * If not provided, the default comparator is (a, b) => a - b. * @param {BTNode | null} [bstRoot] - The root node of the binary search tree. * If not provided, the tree will be initialized as empty. * @param {number} [size] - The size of the binary search tree. * If not provided, the size will be calculated based on the root node. */ constructor(comparator?: BSTComparator, bstRoot?: BTNode, size?: number); /** * Create a BinarySearchTree from an array of entries. * @template K - The type of the keys (number or string) stored in the binary tree nodes. * @template V - The type of the value stored in the binary tree nodes. * @param {Entries} entries - Array of key-value entries. * @param {BSTComparator} [comparator] - The comparator function for keys of the binary search tree. * If not provided, the default comparator is (a, b) => a - b. * @returns {BinarySearchTree} - BinarySearchTree instance. * @timecomplexity O(n log n) - Time complexity of adding many entries individually is O(n log n) * @spacecomplexity O(n) - Linear space complexity as each entry creates a node in the tree. */ static fromEntries(entries: Entries, comparator?: BSTComparator): BinarySearchTree; /** * Create a BinarySearchTree from an array of sorted entries. * @template K - The type of the keys (number or string) stored in the binary tree nodes. * @template V - The type of the value stored in the binary tree nodes. * @param {Entries} entries - Array of key-value entries. * @param {BSTComparator} [comparator] - The comparator function for keys of the binary search tree. * If not provided, the default comparator is (a, b) => a - b. * @returns {BinarySearchTree} - BinarySearchTree instance. * @timecomplexity O(n) - Linear time complexity, where n is the number of numeric entries. * @spacecomplexity O(log n) - Logarithmic space complexity due to the recursive nature of the function. */ static fromSortedEntries(entries: Entries, comparator?: BSTComparator): BinarySearchTree; /** * Get the value associated with a key in the BST. * @param {K} key - Key to search for. * @returns {V | undefined} - Value associated with the key, or undefined if not found. * @timecomplexity O(log n) - Logarithmic time complexity as it navigates through a balanced binary search tree. * @spacecomplexity O(1) - Constant space complexity, as no additional space is used relative to the input size. */ get(key: K): V | undefined; /** * Get the node associated with a key in the BST. * @param {K} key - Key to search for. * @returns {BTNode | null} - Node associated with the key, or null if not found. * @timecomplexity O(log n) - Logarithmic time complexity as it navigates through a balanced binary search tree. * @spacecomplexity O(1) - Constant space complexity, as no additional space is used relative to the input size. */ node(key: K): BTNode | null; /** * Check if a key exists in the BST. * @param {K} key - Key to check. * @returns {boolean} - True if the key exists, false otherwise. * @timecomplexity O(log n) - Logarithmic time complexity as it navigates through a balanced binary search tree. * @spacecomplexity O(1) - Constant space complexity, as no additional space is used relative to the input size. */ has(key: K): boolean; /** * Add a new node with the given key and value to the BST. * @param {K} key - Key to add. * @param {V} val - Value to associate with the key. * @returns {boolean} - True if the node was added successfully, false if the key already exists. * @timecomplexity O(log n) - Logarithmic time complexity as it navigates through a balanced binary search tree. * @spacecomplexity O(log n) - Logarithmic space complexity due to the recursive nature of the function. */ add(key: K, val: V): boolean; /** * Adds multiple nodes with the given keys and values to the BST. * @param {Entries} entries - Array of key-value entries to add. * @returns {number} - Number of entries successfully added. * @timecomplexity O(n log n) - Time complexity of adding many entries individually is O(n log n) * @spacecomplexity O(log n) - Logarithmic space complexity due to the recursive nature of the function. */ addMany(entries: Entries): number; /** * Set the value associated with a key in the BST. * @param {K} key - Key to set the value for * @param {V} val - Value to set * @returns {boolean} - True if the key was found and value set, false otherwise * @timecomplexity O(log n) - Logarithmic time complexity as it navigates through a balanced binary search tree. * @spacecomplexity O(1) - Constant space complexity, as no additional space is used relative to the input size. */ set(key: K, val: V): boolean; /** * Delete a node with the given key from the BST using InOrder successor. * @param {K} key - Key to delete. * @returns {boolean} - True if the node was successfully deleted, false if the key was not found. * @timecomplexity O(log n) - Logarithmic time complexity as it navigates through a balanced binary search tree. * @spacecomplexity O(log n) - Logarithmic space complexity due to the recursive nature of the function. */ delete(key: K): boolean; } declare const numericCompare: BSTComparator; declare const strCompare: BSTComparator; export { BTNode, BinarySearchTree, BinaryTree, DoublyLinkedList, Queue, SinglyLinkedList, Stack, TraversalOrder, numericCompare, strCompare };