Method #insertNode

data_structures/binary_search_tree.ts:358–382

(
    Node: typeof BinarySearchNode,
    value: T,
  )

  }

  #insertNode(
    Node: typeof BinarySearchNode,
    value: T,
  ): BinarySearchNode<T> | null {
    if (!this.#root) {
      this.#root = new Node(null, value);
      this.#size++;
      return this.#root;
    } else {
      let node: BinarySearchNode<T> = this.#root;
      while (true) {
        const order: number = this.#compare(value, node.value);
        if (order === 0) break;
        const direction: Direction = order < 0 ? "left" : "right";
        if (node[direction]) {
          node = node[direction]!;
        } else {
          node[direction] = new Node(node, value);
          this.#size++;
          return node[direction];
        }
      }
    }
    return null;
  }

  /** Removes the given node, and returns the node that was physically removed from the tree. */
  #removeNode(