type-level bst typescript

type-bst.ts

type TreeNode<V extends number = number, L = null, R = null> = {
  value: V;
  left: L;
  right: R;
};

type BinarySearchTree<T = null> = {
  root: T;
};

type Insert<T, V extends number> = T extends null
  ? BinarySearchTree<TreeNode<V>>
  : V extends T['root']['value']
  ? never
  : BinarySearchTree<
      V extends T['root']['value']
        ? TreeNode<V>
        : V extends infer R
        ? R extends T['root']['value']
          ? TreeNode<R>
          : R extends number
          ? TreeNode<
              T['root']['value'],
              Insert<T['root']['left'], R>,
              Insert<T['root']['right'], R>
            >
          : never
        : never
    >;

type Search<T, V extends number> = T extends null
  ? false
  : V extends T['root']['value']
  ? true
  : V extends infer R
  ? R extends T['root']['value']
    ? true
    : R extends number
    ? Search<T['root']['left'], R> | Search<T['root']['right'], R>
    : false
  : false;

type Delete<T, V extends number> = T extends null
  ? never
  : V extends T['root']['value']
  ? BinarySearchTree<
      TreeNode<
        T['root']['value'],
        Delete<T['root']['left'], V>,
        Delete<T['root']['right'], V>
      >
    >
  : BinarySearchTree<
      V extends infer R
      ? R extends T['root']['value']
        ? TreeNode<R>
        : R extends number
        ? TreeNode<
            T['root']['value'],
            Delete<T['root']['left'], R>,
            Delete<T['root']['right'], R>
          >
        : never
      : never
    >;

type InOrder<T> = T extends null
  ? []
  : [...InOrder<T['root']['left']>, T['root']['value'], ...InOrder<T['root']['right']]];