// <template>
class Node(var left: Node?, var right: Node?, var value: Int)
// <template>

fun remove(root: Node?, key: Int): Node? {

    if (root == null) return null
    if (root.value == key) return connectChildTrees(root)

    if (root.value > key) {
        root.left = remove(root.left, key)
    } else {
        root.right = remove(root.right, key)
    }
    return root
}

private fun connectChildTrees(toDel: Node): Node? {
    if (toDel.left == null) return toDel.right
    if (toDel.right == null) return toDel.left

    var connectorParent = toDel
    var connector = toDel.left!!
    while (connector.right != null) {
        connectorParent = connector
        connector = connector.right!!
    }

    // Проверка корнер-кейса, когда самым правым потомком (коннектором) из левой ветви удаляемой вершины получился
    // левый ребёнок удаляемой вершины.
    if (connectorParent === toDel) {
        // В таком случае у коннектора нет правого ребёнка
        assert(connector.right == null)
        // И им должен стать правый ребёнок удаляемой вершины
        connector.right = toDel.right
    } else {
        connectorParent.right = connector.left
        connector.left = toDel.left
        connector.right = toDel.right
    }

    return connector
}