sealed interface BST<K extends Comparable<? super K>, V> {

    record EmptyBST<K extends Comparable<? super K>, V>() implements BST<K, V> {
    }

    record NodeBST<K extends Comparable<? super K>, V>(K key, V value,
                                                       BST<K, V> left, BST<K, V> right) implements BST<K, V> {
    }

    static <K extends Comparable<? super K>, V> BST<K, V> empty() {
        return new EmptyBST<>();
    }

    default BST<K, V> insert(K k, V v) {
        return switch (this) {
            case EmptyBST<K, V>() -> new NodeBST<>(k, v, empty(), empty());
            case NodeBST<K, V>(K key,V value,BST<K, V> left,BST<K, V> right) ->
                    switch (Integer.valueOf(k.compareTo(key))) {
                        case Integer i when i < 0 -> new NodeBST<>(key, value, left.insert(k, v), right);
                        case Integer i when i > 0 -> new NodeBST<>(key, value, left, right.insert(k, v));
                        default -> this;
                    };
        };
    }
}