/**
 * data-structure-typed
 *
 * @author Pablo Zeng
 * @copyright Copyright (c) 2022 Pablo Zeng <zrwusa@gmail.com>
 * @license MIT License
 */
import type { BSTNOptKeyOrNode, BSTOptions, BTNRep, Comparator, DFSOrderPattern, EntryCallback, FamilyPosition, IterationType, NodeCallback, NodePredicate, OptNode, RBTNColor } from '../../types';
import { BinaryTree } from './binary-tree';
import { IBinaryTree } from '../../interfaces';
import { Range } from '../../common';
/**
 * Represents a Node in a Binary Search Tree.
 *
 * @template K - The type of the key.
 * @template V - The type of the value.
 */
export declare class BSTNode<K = any, V = any> {
    key: K;
    value?: V;
    parent?: BSTNode<K, V>;
    /**
     * Creates an instance of BSTNode.
     * @remarks Time O(1), Space O(1)
     *
     * @param key - The key of the node.
     * @param [value] - The value associated with the key.
     */
    constructor(key: K, value?: V);
    _left?: BSTNode<K, V> | null | undefined;
    /**
     * Gets the left child of the node.
     * @remarks Time O(1), Space O(1)
     *
     * @returns The left child.
     */
    get left(): BSTNode<K, V> | null | undefined;
    /**
     * Sets the left child of the node and updates its parent reference.
     * @remarks Time O(1), Space O(1)
     *
     * @param v - The node to set as the left child.
     */
    set left(v: BSTNode<K, V> | null | undefined);
    _right?: BSTNode<K, V> | null | undefined;
    /**
     * Gets the right child of the node.
     * @remarks Time O(1), Space O(1)
     *
     * @returns The right child.
     */
    get right(): BSTNode<K, V> | null | undefined;
    /**
     * Sets the right child of the node and updates its parent reference.
     * @remarks Time O(1), Space O(1)
     *
     * @param v - The node to set as the right child.
     */
    set right(v: BSTNode<K, V> | null | undefined);
    _height: number;
    /**
     * Gets the height of the node (used in self-balancing trees).
     * @remarks Time O(1), Space O(1)
     *
     * @returns The height.
     */
    get height(): number;
    /**
     * Sets the height of the node.
     * @remarks Time O(1), Space O(1)
     *
     * @param value - The new height.
     */
    set height(value: number);
    _color: RBTNColor;
    /**
     * Gets the color of the node (used in Red-Black trees).
     * @remarks Time O(1), Space O(1)
     *
     * @returns The node's color.
     */
    get color(): RBTNColor;
    /**
     * Sets the color of the node.
     * @remarks Time O(1), Space O(1)
     *
     * @param value - The new color.
     */
    set color(value: RBTNColor);
    _count: number;
    /**
     * Gets the count of nodes in the subtree rooted at this node (used in order-statistic trees).
     * @remarks Time O(1), Space O(1)
     *
     * @returns The subtree node count.
     */
    get count(): number;
    /**
     * Sets the count of nodes in the subtree.
     * @remarks Time O(1), Space O(1)
     *
     * @param value - The new count.
     */
    set count(value: number);
    /**
     * Gets the position of the node relative to its parent.
     * @remarks Time O(1), Space O(1)
     *
     * @returns The family position (e.g., 'ROOT', 'LEFT', 'RIGHT').
     */
    get familyPosition(): FamilyPosition;
}
/**
 * Represents a Binary Search Tree (BST).
 * Keys are ordered, allowing for faster search operations compared to a standard Binary Tree.
 * @template K - The type of the key.
 * @template V - The type of the value.
 * @template R - The type of the raw data object (if using `toEntryFn`).
 *
 * 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
 * // BST delete and search after deletion
 *  const bst = new BST<number>([11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5]);
 *
 *     // Delete a leaf node
 *     bst.delete(1);
 *     console.log(bst.has(1)); // false;
 *
 *     // Delete a node with one child
 *     bst.delete(2);
 *     console.log(bst.has(2)); // false;
 *
 *     // Delete a node with two children
 *     bst.delete(3);
 *     console.log(bst.has(3)); // false;
 *
 *     // Size decreases with each deletion
 *     console.log(bst.size); // 13;
 *
 *     // Other nodes remain searchable
 *     console.log(bst.has(11)); // true;
 *     console.log(bst.has(15)); // true;
 * @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.setMany(dataset2);
 *     merged.merge(dataset3);
 *
 *     // Verify merged dataset is in sorted order
 *     console.log([...merged.values()]); // ['A', 'B', 'C', 'D', 'E', 'F', 'G'];
 * @example
 * // BST with custom objects for expression evaluation
 *  interface Expression {
 *       id: number;
 *       operator: string;
 *       precedence: number;
 *     }
 *
 *     // BST efficiently stores and retrieves operators by precedence
 *     const operatorTree = new BST<number, Expression>(
 *       [
 *         [1, { id: 1, operator: '+', precedence: 1 }],
 *         [2, { id: 2, operator: '*', precedence: 2 }],
 *         [3, { id: 3, operator: '/', precedence: 2 }],
 *         [4, { id: 4, operator: '-', precedence: 1 }],
 *         [5, { id: 5, operator: '^', precedence: 3 }]
 *       ],
 *       { isMapMode: false }
 *     );
 *
 *     console.log(operatorTree.size); // 5;
 *
 *     // Quick lookup of operators
 *     const mult = operatorTree.get(2);
 *     console.log(mult?.operator); // '*';
 *     console.log(mult?.precedence); // 2;
 *
 *     // Check if operator exists
 *     console.log(operatorTree.has(5)); // true;
 *     console.log(operatorTree.has(99)); // false;
 *
 *     // Retrieve operator by precedence level
 *     const expNode = operatorTree.getNode(3);
 *     console.log(expNode?.key); // 3;
 *     console.log(expNode?.value?.precedence); // 2;
 *
 *     // Delete operator and verify
 *     operatorTree.delete(1);
 *     console.log(operatorTree.has(1)); // false;
 *     console.log(operatorTree.size); // 4;
 *
 *     // Get tree height for optimization analysis
 *     const treeHeight = operatorTree.getHeight();
 *     console.log(treeHeight); // > 0;
 *
 *     // Remaining operators are still accessible
 *     const remaining = operatorTree.get(2);
 *     console.log(remaining); // defined;
 * @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 | undefined)[], arr2: (number | undefined)[]): 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;
 */
export declare class BST<K = any, V = any, R = any> extends BinaryTree<K, V, R> implements IBinaryTree<K, V, R> {
    /**
     * Creates an instance of BST.
     * @remarks Time O(N log N) or O(N^2) depending on `isBalanceAdd` in `addMany` and input order. Space O(N).
     *
     * @param [keysNodesEntriesOrRaws=[]] - An iterable of items to set.
     * @param [options] - Configuration options for the BST, including comparator.
     */
    constructor(keysNodesEntriesOrRaws?: Iterable<K | BSTNode | [K | null | undefined, V | undefined] | null | undefined | R>, options?: BSTOptions<K, V, R>);
    protected _root?: BSTNode<K, V>;
    protected _enableOrderStatistic: boolean;
    /**
     * Gets the root node of the tree.
     * @remarks Time O(1)
     *
     * @returns The root node.
     */
    get root(): OptNode<BSTNode<K, V>>;
    /**
     * The comparator function used to determine the order of keys in the tree.
  
     * @remarks Time O(1) Space O(1)
     */
    protected readonly _comparator: Comparator<K>;
    /**
     * Gets the comparator function used by the tree.
     * @remarks Time O(1)
     *
     * @returns The comparator function.
     */
    get comparator(): Comparator<K>;
    /**
     * (Protected) Creates a new BST node.
     * @remarks Time O(1), Space O(1)
     *
     * @param key - The key for the new node.
     * @param [value] - The value for the new node (used if not in Map mode).
     * @returns The newly created BSTNode.
     */
    createNode(key: K, value?: V): BSTNode<K, V>;
    /**
     * Ensures the input is a node. If it's a key or entry, it searches for the node.
     * @remarks Time O(log N) (height of the tree), O(N) worst-case.
     *
     * @param keyNodeOrEntry - The item to resolve to a node.
     * @param [iterationType=this.iterationType] - The traversal method to use if searching.
     * @returns The resolved node, or undefined if not found.
     */
    ensureNode(keyNodeOrEntry: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined, iterationType?: IterationType): OptNode<BSTNode<K, V>>;
    /**
     * Checks if the given item is a `BSTNode` instance.
     * @remarks Time O(1), Space O(1)
     *
     * @param keyNodeOrEntry - The item to check.
     * @returns True if it's a BSTNode, false otherwise.
     */
    isNode(keyNodeOrEntry: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined): keyNodeOrEntry is BSTNode<K, V>;
    /**
     * Checks if the given key is valid (comparable).
     * @remarks Time O(1)
     *
     * @param key - The key to validate.
     * @returns True if the key is valid, false otherwise.
     */
    isValidKey(key: unknown): key is K;
    /**
   * Depth-first search traversal
  
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
    * @example
 * // Depth-first traversal
 *  const bst = new BST<number>([5, 3, 7, 1, 4]);
 *     const inOrder = bst.dfs(node => node.key, 'IN');
 *     console.log(inOrder); // [1, 3, 4, 5, 7];
   */
    dfs(): (K | undefined)[];
    dfs<C extends NodeCallback<BSTNode<K, V>>>(callback: C, pattern?: DFSOrderPattern, onlyOne?: boolean, startNode?: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined, iterationType?: IterationType): ReturnType<C>[];
    /**
   * BinaryTree level-order traversal
  
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
    * @example
 * // Breadth-first traversal
 *  const bst = new BST<number>([5, 3, 7]);
 *     const result = bst.bfs(node => node.key);
 *     console.log(result.length); // 3;
   */
    bfs(): (K | undefined)[];
    bfs<C extends NodeCallback<BSTNode<K, V>>>(callback: C, startNode?: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined, iterationType?: IterationType): ReturnType<C>[];
    /**
   * Level-order grouping
  
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
    * @example
 * // Level-order grouping
 *  const bst = new BST<number>([5, 3, 7, 1, 4]);
 *     const levels = bst.listLevels(node => node.key);
 *     console.log(levels); // toBeInstanceOf;
 *     console.log(levels[0].length); // 1; // root level has 1 node
 *     const allKeys = levels.flat().sort((a, b) => a - b);
 *     console.log(allKeys); // [1, 3, 4, 5, 7];
   */
    listLevels(): (K | undefined)[][];
    listLevels<C extends NodeCallback<BSTNode<K, V>>>(callback: C, startNode?: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined, iterationType?: IterationType): ReturnType<C>[][];
    /**
     * Gets the first node matching a predicate.
     * @remarks Time O(log N) if searching by key, O(N) if searching by predicate. Space O(log N) or O(N).
     *
     * @param keyNodeEntryOrPredicate - The key, node, entry, or predicate function to search for.
     * @param [startNode=this._root] - The node to start the search from.
     * @param [iterationType=this.iterationType] - The traversal method.
     * @returns The first matching node, or undefined if not found.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Get node object by key
   *  const bst = new BST<number, string>([[5, 'root'], [3, 'left'], [7, 'right']]);
   *     const node = bst.getNode(3);
   *     console.log(node?.key); // 3;
   *     console.log(node?.value); // 'left';
     */
    getNode(keyNodeEntryOrPredicate: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined | NodePredicate<BSTNode<K, V>>, startNode?: BSTNOptKeyOrNode<K, BSTNode<K, V>>, iterationType?: IterationType): OptNode<BSTNode<K, V>>;
    /**
   * Search nodes by predicate
  
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
    * @example
 * // Search nodes by predicate
 *  const bst = new BST<number, string>([[1, 'a'], [2, 'b'], [3, 'c'], [4, 'd']]);
 *     const found = bst.search(node => node.key > 2, true);
 *     console.log(found.length); // >= 1;
   */
    search(keyNodeEntryOrPredicate: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined | NodePredicate<BSTNode<K, V>> | Range<K>, onlyOne?: boolean): (K | undefined)[];
    search<C extends NodeCallback<BSTNode<K, V>>>(keyNodeEntryOrPredicate: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined | NodePredicate<BSTNode<K, V>> | Range<K>, onlyOne: boolean, callback: C, startNode?: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined, iterationType?: IterationType): ReturnType<C>[];
    /**
   * Find all keys in a range
  
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
    * @example
 * // Find all keys in a range
 *  const bst = new BST<number>([10, 20, 30, 40, 50]);
 *     console.log(bst.rangeSearch([15, 35])); // [20, 30];
   */
    rangeSearch(range: Range<K> | [K, K]): (K | undefined)[];
    rangeSearch<C extends NodeCallback<BSTNode<K, V>>>(range: Range<K> | [K, K], callback: C, startNode?: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined, iterationType?: IterationType): ReturnType<C>[];
    /**
     * Returns the element at the k-th position in tree order (0-indexed).
     * @remarks Time O(log n), Space O(1) iterative / O(log n) recursive. Requires `enableOrderStatistic: true`.
     * Tree order is defined by the comparator — ascending by default, but respects custom comparators (e.g. descending).
     *
     * @param k - The 0-based position in tree order (0 = first element).
     * @returns The key at position k, or `undefined` if out of bounds.
      * @example
   * // Order-statistic on BST
   *  const tree = new BST<number>([30, 10, 50, 20, 40], { enableOrderStatistic: true });
   *       console.log(tree.getByRank(0)); // 10;
   *       console.log(tree.getByRank(4)); // 50;
   *       console.log(tree.getRank(30)); // 2;
     */
    getByRank(k: number): K | undefined;
    /**
     * Returns the element at the k-th position in tree order and applies a callback.
     * @remarks Time O(log n), Space O(1) iterative / O(log n) recursive. Requires `enableOrderStatistic: true`.
     *
     * @param k - The 0-based position in tree order (0 = first element).
     * @param callback - Callback to apply to the found node.
     * @param iterationType - Iteration strategy ('ITERATIVE' or 'RECURSIVE').
     * @returns The callback result, or `undefined` if out of bounds.
     */
    getByRank<C extends NodeCallback<BSTNode<K, V>>>(k: number, callback: C, iterationType?: IterationType): ReturnType<C> | undefined;
    /**
     * Returns the 0-based rank of a key (number of elements that precede it in tree order).
     * @remarks Time O(log n), Space O(1) iterative / O(log n) recursive. Requires `enableOrderStatistic: true`.
     * Tree order is defined by the comparator. When the key is not found, returns the insertion position.
     *
     * @param keyNodeEntryOrPredicate - The key, node, entry `[K, V]`, or predicate to find.
     * @returns The rank (0-indexed), or -1 if the tree is empty or input is invalid.
     */
    getRank(keyNodeEntryOrPredicate: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined | NodePredicate<BSTNode<K, V>>): number;
    /**
     * Returns the 0-based rank (number of preceding elements in tree order) with explicit iteration type.
     * @remarks Time O(log n), Space O(1) iterative / O(log n) recursive. Requires `enableOrderStatistic: true`.
     *
     * @param keyNodeEntryOrPredicate - The key, node, entry, or predicate to find.
     * @param iterationType - Iteration strategy ('ITERATIVE' or 'RECURSIVE').
     * @returns The rank (0-indexed), or -1 if the tree is empty or input is invalid.
     */
    getRank(keyNodeEntryOrPredicate: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined | NodePredicate<BSTNode<K, V>>, iterationType: IterationType): number;
    /**
     * Returns elements by position range in tree order (0-indexed, inclusive on both ends).
     * @remarks Time O(log n + k), Space O(k), where k = end - start + 1. Requires `enableOrderStatistic: true`.
     *
     * @param start - Start position (inclusive, 0-indexed). Clamped to 0 if negative.
     * @param end - End position (inclusive, 0-indexed). Clamped to size-1 if too large.
     * @returns Array of keys in tree order within the specified range.
     */
    rangeByRank(start: number, end: number): (K | undefined)[];
    /**
     * Returns elements by position range in tree order with callback and optional iteration type.
     * @remarks Time O(log n + k), Space O(k), where k = end - start + 1. Requires `enableOrderStatistic: true`.
     *
     * @param start - Start rank (inclusive, 0-indexed).
     * @param end - End rank (inclusive, 0-indexed).
     * @param callback - Callback to apply to each node in the range.
     * @param iterationType - Iteration strategy ('ITERATIVE' or 'RECURSIVE').
     * @returns Array of callback results for nodes in the rank range.
     */
    rangeByRank<C extends NodeCallback<BSTNode<K, V>>>(start: number, end: number, callback: C, iterationType?: IterationType): ReturnType<C>[];
    /**
     * Adds a new node to the BST based on key comparison.
     * @remarks Time O(log N), where H is tree height. O(N) worst-case (unbalanced tree), O(log N) average. Space O(1).
     *
     * @param keyNodeOrEntry - The key, node, or entry to set.
     * @param [value] - The value, if providing just a key.
     * @returns True if the addition was successful, false otherwise.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Set a key-value pair
   *  const bst = new BST<number, string>();
   *     bst.set(1, 'one');
   *     bst.set(2, 'two');
   *     console.log(bst.get(1)); // 'one';
     */
    set(keyNodeOrEntry: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined, value?: V): boolean;
    /**
     * Adds multiple items to the tree.
     * @remarks If `isBalanceAdd` is true, sorts the input and builds a balanced tree. Time O(N log N) (due to sort and balanced set).
     * If false, adds items one by one. Time O(N * H), which is O(N^2) worst-case.
     * Space O(N) for sorting and recursion/iteration stack.
     *
     * @param keysNodesEntriesOrRaws - An iterable of items to set.
     * @param [values] - An optional parallel iterable of values.
     * @param [isBalanceAdd=true] - If true, builds a balanced tree from the items.
     * @param [iterationType=this.iterationType] - The traversal method for balanced set (recursive or iterative).
     * @returns An array of booleans indicating the success of each individual `set` operation.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Set multiple key-value pairs
   *  const bst = new BST<number, string>();
   *     bst.setMany([[1, 'a'], [2, 'b'], [3, 'c']]);
   *     console.log(bst.size); // 3;
   *     console.log(bst.get(2)); // 'b';
     */
    setMany(keysNodesEntriesOrRaws: Iterable<R | BTNRep<K, V, BSTNode<K, V>>>, values?: Iterable<V | undefined>, isBalanceAdd?: boolean, iterationType?: IterationType): boolean[];
    /**
     * Returns the first key with a value >= target.
     * Equivalent to Java TreeMap.ceiling.
     * Time Complexity: O(log n) average, O(h) worst case.
     * Space Complexity: O(h) for recursion, O(1) for iteration.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Find the least key ≥ target
   *  const bst = new BST<number>([10, 20, 30, 40, 50]);
   *     console.log(bst.ceiling(25)); // 30;
   *     console.log(bst.ceiling(30)); // 30;
   *     console.log(bst.ceiling(55)); // undefined;
     */
    ceiling(keyNodeEntryOrPredicate: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined | NodePredicate<BSTNode<K, V>>): K | undefined;
    /**
     * Returns the first node with a key >= target and applies callback.
     * Time Complexity: O(log n) average, O(h) worst case.
     * Space Complexity: O(h) for recursion, O(1) for iteration.
     */
    ceiling<C extends NodeCallback<BSTNode<K, V>>>(keyNodeEntryOrPredicate: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined | NodePredicate<BSTNode<K, V>>, callback: C, iterationType?: IterationType): ReturnType<C>;
    /**
     * Returns the first key with a value > target.
     * Equivalent to Java TreeMap.higher.
     * Time Complexity: O(log n) average, O(h) worst case.
     * Space Complexity: O(h) for recursion, O(1) for iteration.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Find the least key strictly > target
   *  const bst = new BST<number>([10, 20, 30, 40]);
   *     console.log(bst.higher(20)); // 30;
   *     console.log(bst.higher(40)); // undefined;
     */
    higher(keyNodeEntryOrPredicate: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined | NodePredicate<BSTNode<K, V>>): K | undefined;
    /**
     * Returns the first node with a key > target and applies callback.
     * Time Complexity: O(log n) average, O(h) worst case.
     * Space Complexity: O(h) for recursion, O(1) for iteration.
     */
    higher<C extends NodeCallback<BSTNode<K, V>>>(keyNodeEntryOrPredicate: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined | NodePredicate<BSTNode<K, V>>, callback: C, iterationType?: IterationType): ReturnType<C>;
    /**
     * Returns the first key with a value <= target.
     * Equivalent to Java TreeMap.floor.
     * Time Complexity: O(log n) average, O(h) worst case.
     * Space Complexity: O(h) for recursion, O(1) for iteration.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Find the greatest key ≤ target
   *  const bst = new BST<number>([10, 20, 30, 40, 50]);
   *     console.log(bst.floor(25)); // 20;
   *     console.log(bst.floor(10)); // 10;
   *     console.log(bst.floor(5)); // undefined;
     */
    floor(keyNodeEntryOrPredicate: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined | NodePredicate<BSTNode<K, V>>): K | undefined;
    /**
     * Returns the first node with a key <= target and applies callback.
     * Time Complexity: O(log n) average, O(h) worst case.
     * Space Complexity: O(h) for recursion, O(1) for iteration.
     */
    floor<C extends NodeCallback<BSTNode<K, V>>>(keyNodeEntryOrPredicate: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined | NodePredicate<BSTNode<K, V>>, callback: C, iterationType?: IterationType): ReturnType<C>;
    /**
     * Returns the first key with a value < target.
     * Equivalent to Java TreeMap.lower.
     * Time Complexity: O(log n) average, O(h) worst case.
     * Space Complexity: O(h) for recursion, O(1) for iteration.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Find the greatest key strictly < target
   *  const bst = new BST<number>([10, 20, 30, 40]);
   *     console.log(bst.lower(30)); // 20;
   *     console.log(bst.lower(10)); // undefined;
     */
    lower(keyNodeEntryOrPredicate: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined | NodePredicate<BSTNode<K, V>>): K | undefined;
    /**
     * Returns the first node with a key < target and applies callback.
     * Time Complexity: O(log n) average, O(h) worst case.
     * Space Complexity: O(h) for recursion, O(1) for iteration.
     */
    lower<C extends NodeCallback<BSTNode<K, V>>>(keyNodeEntryOrPredicate: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined | NodePredicate<BSTNode<K, V>>, callback: C, iterationType?: IterationType): ReturnType<C>;
    lesserOrGreaterTraverse(): (K | undefined)[];
    lesserOrGreaterTraverse<C extends NodeCallback<BSTNode<K, V>>>(callback: C, lesserOrGreater?: number, targetNode?: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined, iterationType?: IterationType): ReturnType<C>[];
    /**
     * Rebuilds the tree to be perfectly balanced.
     * @remarks Time O(N) (O(N) for DFS, O(N) for sorted build). Space O(N) for node array and recursion stack.
     *
     * @param [iterationType=this.iterationType] - The traversal method for the initial node export.
     * @returns True if successful, false if the tree was empty.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Rebalance the tree
   *  const bst = new BST<number>();
   *     // Insert in sorted order (worst case for BST)
   *     for (let i = 1; i <= 7; i++) bst.add(i);
   *     console.log(bst.isAVLBalanced()); // false;
   *     bst.perfectlyBalance();
   *     console.log(bst.isAVLBalanced()); // true;
     */
    perfectlyBalance(iterationType?: IterationType): boolean;
    /**
     * Checks if the tree meets the AVL balance condition (height difference <= 1).
     * @remarks Time O(N), as it must visit every node to compute height. Space O(log N) for recursion or O(N) for iterative map.
     *
     * @param [iterationType=this.iterationType] - The traversal method.
     * @returns True if the tree is AVL balanced, false otherwise.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Check if tree is height-balanced
   *  const bst = new BST<number>([3, 1, 5, 2, 4]);
   *     console.log(bst.isAVLBalanced()); // true;
     */
    isAVLBalanced(iterationType?: IterationType): boolean;
    /**
     * Creates a new BST by mapping each [key, value] pair to a new entry.
     * @remarks Time O(N * H), where N is nodes in this tree, and H is height of the new tree during insertion.
     * Space O(N) for the new tree.
     *
     * @template MK - New key type.
     * @template MV - New value type.
     * @template MR - New raw type.
     * @param callback - A function to map each [key, value] pair.
     * @param [options] - Options for the new BST.
     * @param [thisArg] - `this` context for the callback.
     * @returns A new, mapped BST.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Transform to new tree
   *  const bst = new BST<number, number>([[1, 10], [2, 20], [3, 30]]);
   *     const doubled = bst.map((value, key) => [key, (value ?? 0) * 2] as [number, number]);
   *     console.log([...doubled.values()]); // [20, 40, 60];
     */
    map<MK = K, MV = V, MR = any>(callback: EntryCallback<K, V | undefined, [MK, MV]>, options?: Partial<BSTOptions<MK, MV, MR>>, thisArg?: unknown): BST<MK, MV, MR>;
    /**
     * Deletes nodes that match a key, node, entry, predicate, or range.
     *
     * @remarks
     * Time Complexity: O(N) for search + O(M log N) for M deletions, where N is tree size.
     * Space Complexity: O(M) for storing matched nodes and result map.
     *
     * @template K - The key type.
     * @template V - The value type.
     *
     * @param keyNodeEntryOrPredicate - The search criteria. Can be one of:
     *   - A key (type K): searches for exact key match using the comparator.
     *   - A BSTNode: searches for the matching node in the tree.
     *   - An entry tuple: searches for the key-value pair.
     *   - A NodePredicate function: tests each node and returns true for matches.
     *   - A Range object: searches for nodes whose keys fall within the specified range (inclusive/exclusive based on range settings).
     *   - null or undefined: treated as no match, returns empty results.
     *
     * @param onlyOne - If true, stops the search after finding the first match and only deletes that one node.
     *   If false (default), searches for and deletes all matching nodes.
     *
     * @param startNode - The node to start the search from. Can be:
     *   - A key, node, or entry: the method resolves it to a node and searches from that subtree.
     *   - null or undefined: defaults to the root, searching the entire tree.
     *   - Default value: this._root (the tree's root).
     *
     * @param iterationType - Controls the internal traversal implementation:
     *   - 'RECURSIVE': uses recursive function calls for traversal.
     *   - 'ITERATIVE': uses explicit stack-based iteration.
     *   - Default: this.iterationType (the tree's default iteration mode).
     *
     * @returns A Map<K, boolean> containing the deletion results:
     *   - Key: the matched node's key.
     *   - Value: true if the deletion succeeded, false if it failed (e.g., key not found during deletion phase).
     *   - If no nodes match the search criteria, the returned map is empty.
     */
    deleteWhere(keyNodeEntryOrPredicate: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined | NodePredicate<BSTNode<K, V>> | Range<K>, onlyOne?: boolean, startNode?: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined, iterationType?: IterationType): boolean;
    /**
     * (Protected) Creates the default comparator function for keys that don't have a custom comparator.
     * @remarks Time O(1) Space O(1)
     * @returns The default comparator function.
     */
    protected _createDefaultComparator(): Comparator<K>;
    /**
     * (Protected) Binary search for floor by key with pruning optimization.
     * Performs standard BST binary search, choosing left or right subtree based on comparator result.
     * Finds first node where key <= target.
     * @remarks Time O(h) where h is tree height.
     *
     * @param key - The target key to search for.
     * @param iterationType - The iteration type (RECURSIVE or ITERATIVE).
     * @returns The first node with key <= target, or undefined if none exists.
     */
    protected _floorByKey(key: K, iterationType: IterationType): BSTNode<K, V> | undefined;
    /**
     * (Protected) In-order traversal search for floor by predicate.
     * Falls back to linear in-order traversal when predicate-based search is required.
     * Returns the last node that satisfies the predicate function.
     * @remarks Time Complexity: O(n) since it may visit every node.
     * Space Complexity: O(h) for recursion, O(h) for iterative stack.
     *
     * @param predicate - The predicate function to test nodes.
     * @param iterationType - The iteration type (RECURSIVE or ITERATIVE).
     * @returns The last node satisfying predicate (highest key), or undefined if none found.
     */
    protected _floorByPredicate(predicate: NodePredicate<BSTNode<K, V>>, iterationType: IterationType): BSTNode<K, V> | undefined;
    /**
     * (Protected) Binary search for lower by key with pruning optimization.
     * Performs standard BST binary search, choosing left or right subtree based on comparator result.
     * Finds first node where key < target.
     * @remarks Time O(h) where h is tree height.
     *
     * @param key - The target key to search for.
     * @param iterationType - The iteration type (RECURSIVE or ITERATIVE).
     * @returns The first node with key < target, or undefined if none exists.
     */
    protected _lowerByKey(key: K, iterationType: IterationType): BSTNode<K, V> | undefined;
    /**
     * (Protected) In-order traversal search for lower by predicate.
     * Falls back to linear in-order traversal when predicate-based search is required.
     * Returns the node that satisfies the predicate and appears last in in-order traversal.
     * @remarks Time Complexity: O(n) since it may visit every node.
     * Space Complexity: O(h) for recursion, O(h) for iterative stack.
     *
     * @param predicate - The predicate function to test nodes.
     * @param iterationType - The iteration type (RECURSIVE or ITERATIVE).
     * @returns The last node satisfying predicate (highest key < target), or undefined if none found.
     */
    protected _lowerByPredicate(predicate: NodePredicate<BSTNode<K, V>>, iterationType: IterationType): BSTNode<K, V> | undefined;
    /**
     * (Protected) Core bound search implementation supporting all parameter types.
     * Unified logic for both lowerBound and upperBound.
     * Resolves various input types (Key, Node, Entry, Predicate) using parent class utilities.
     * @param keyNodeEntryOrPredicate - The key, node, entry, or predicate function to search for.
     * @param isLower - True for lowerBound (>=), false for upperBound (>).
     * @param iterationType - The iteration type (RECURSIVE or ITERATIVE).
     * @returns The first matching node, or undefined if no such node exists.
     */
    protected _bound(keyNodeEntryOrPredicate: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined | NodePredicate<BSTNode<K, V>>, isLower: boolean, iterationType: IterationType): BSTNode<K, V> | undefined;
    /**
     * (Protected) Binary search for bound by key with pruning optimization.
     * Performs standard BST binary search, choosing left or right subtree based on comparator result.
     * For lowerBound: finds first node where key >= target.
     * For upperBound: finds first node where key > target.
     * @param key - The target key to search for.
     * @param isLower - True for lowerBound (>=), false for upperBound (>).
     * @param iterationType - The iteration type (RECURSIVE or ITERATIVE).
     * @returns The first node matching the bound condition, or undefined if none exists.
     */
    protected _boundByKey(key: K, isLower: boolean, iterationType: IterationType): BSTNode<K, V> | undefined;
    /**
     * (Protected) In-order traversal search by predicate.
     * Falls back to linear in-order traversal when predicate-based search is required.
     * Returns the first node that satisfies the predicate function.
     * Note: Predicate-based search cannot leverage BST's binary search optimization.
     * Time Complexity: O(n) since it may visit every node.
     * @param predicate - The predicate function to test nodes.
     * @param iterationType - The iteration type (RECURSIVE or ITERATIVE).
     * @returns The first node satisfying predicate, or undefined if none found.
     */
    protected _boundByPredicate(predicate: NodePredicate<BSTNode<K, V>>, iterationType: IterationType): BSTNode<K, V> | undefined;
    /**
     * (Protected) Creates a new, empty instance of the same BST constructor.
     * @remarks Time O(1)
     *
     * @template TK, TV, TR - Generic types for the new instance.
     * @param [options] - Options for the new BST.
     * @returns A new, empty BST.
     */
    protected _createInstance<TK = K, TV = V, TR = R>(options?: Partial<BSTOptions<TK, TV, TR>>): this;
    /**
     * (Protected) Creates a new instance of the same BST constructor, potentially with different generic types.
     * @remarks Time O(N log N) or O(N^2) (from constructor) due to processing the iterable.
     *
     * @template TK, TV, TR - Generic types for the new instance.
     * @param [iter=[]] - An iterable to populate the new BST.
     * @param [options] - Options for the new BST.
     * @returns A new BST.
     */
    protected _createLike<TK = K, TV = V, TR = R>(iter?: Iterable<TK | BSTNode<TK, TV> | [TK | null | undefined, TV | undefined] | null | undefined | TR>, options?: Partial<BSTOptions<TK, TV, TR>>): BST<TK, TV, TR>;
    /**
     * (Protected) Snapshots the current BST's configuration options.
     * @remarks Time O(1)
     *
     * @template TK, TV, TR - Generic types for the options.
     * @returns The options object.
     */
    protected _snapshotOptions<TK = K, TV = V, TR = R>(): BSTOptions<TK, TV, TR>;
    /**
     * (Protected) Converts a key, node, or entry into a standardized [node, value] tuple.
     * @remarks Time O(1)
     *
     * @param keyNodeOrEntry - The input item.
     * @param [value] - An optional value (used if input is just a key).
     * @returns A tuple of [node, value].
     */
    protected _keyValueNodeOrEntryToNodeAndValue(keyNodeOrEntry: K | BSTNode<K, V> | [K | null | undefined, V | undefined] | null | undefined, value?: V): [OptNode<BSTNode<K, V>>, V | undefined];
    /**
     * (Protected) Sets the root node and clears its parent reference.
     * @remarks Time O(1)
     *
     * @param v - The node to set as root.
     */
    /**
     * (Protected) Recalculates the subtree count for a single node.
     * @remarks Time O(1). Only active when enableOrderStatistic is true.
     */
    protected _updateCount(node: BSTNode<K, V>): void;
    /**
     * (Protected) Updates subtree counts from a node up to the root.
     * @remarks Time O(log n). Only active when enableOrderStatistic is true.
     */
    protected _updateCountAlongPath(node: OptNode<BSTNode<K, V>>): void;
    /**
     * (Protected) Finds the node at position k in tree order (iterative).
     * @remarks Time O(log n), Space O(1)
     */
    protected _getByRankIterative(node: OptNode<BSTNode<K, V>>, k: number): BSTNode<K, V> | undefined;
    /**
     * (Protected) Finds the node at position k in tree order (recursive).
     * @remarks Time O(log n), Space O(log n) call stack
     */
    protected _getByRankRecursive(node: OptNode<BSTNode<K, V>>, k: number): BSTNode<K, V> | undefined;
    /**
     * (Protected) Computes the rank of a key iteratively.
     * @remarks Time O(log n), Space O(1)
     */
    protected _getRankIterative(node: OptNode<BSTNode<K, V>>, key: K): number;
    /**
     * (Protected) Computes the rank of a key recursively.
     * @remarks Time O(log n), Space O(log n) call stack
     */
    protected _getRankRecursive(node: OptNode<BSTNode<K, V>>, key: K): number;
    /**
     * (Protected) Finds the in-order successor of a node.
     * @remarks Time O(log n), Space O(1)
     */
    protected _next(node: BSTNode<K, V>): BSTNode<K, V> | undefined;
    protected _setRoot(v: OptNode<BSTNode<K, V>>): void;
    /**
     * (Protected) Compares two keys using the tree's comparator and reverse setting.
     * @remarks Time O(1) Space O(1)
     *
     * @param a - The first key.
     * @param b - The second key.
     * @returns A number (1, -1, or 0) representing the comparison.
     */
    protected _compare(a: K, b: K): number;
    /**
     * (Private) Deletes a node by its key.
     * @remarks Standard BST deletion algorithm. Time O(log N), O(N) worst-case. Space O(1).
     *
     * @param key - The key of the node to delete.
     * @returns True if the node was found and deleted, false otherwise.
     */
    protected _deleteByKey(key: K): boolean;
}