Method #findNode

data_structures/unstable_binary_search_tree.ts:243–273

* Finds the node matching the given selection criteria. * * When searching for higher nodes, returns the lowest node that is higher than * the value. When searching for lower nodes, returns the highest node that is * lower than the value. * * By default, only accepts a node exactly

(
    value: T,
    select?: "higher" | "lower",
    returnIfFound: boolean = true,
  )

   * @returns The node that matched, or null if none matched
   */
  #findNode(
    value: T,
    select?: "higher" | "lower",
    returnIfFound: boolean = true,
  ): BinarySearchNode<T> | null {
    const compare = getCompare(this);

    let node: BinarySearchNode<T> | null = getRoot(this);
    let result: BinarySearchNode<T> | null = null;
    while (node) {
      const order = compare(value, node.value);
      if (order === 0 && returnIfFound) return node;

      let direction: Direction = order < 0 ? "left" : "right";
      if (select === "higher" && order === 0) {
        direction = "right";
      } else if (select === "lower" && order === 0) {
        direction = "left";
      }

      if (
        (select === "higher" && direction === "left") ||
        (select === "lower" && direction === "right")
      ) {
        result = node;
      }

      node = node[direction];
    }
    return result;
  }

  /**
   * Finds the lowest (leftmost) value in the binary search tree which is