tree-split

fun split(root: Node?, k: Int): List<Node?> {
    // Вычисляем размер левого поддерева с учётом того,
    // что оно может быть пустым.
    val leftSize = if (root?.left == null) 0 else root.left!!.size
    // Если слева ровно k вершин, то искомая вершина - корень консистентного дерева
    if (leftSize == k || k == root?.size) {
        return listOf(root, null)
    }
    // левое поддерево слишком мало
    return if (leftSize < k) {
        // root выше слева
        // поиск в правом поддереве
        val result = split(root!!.right, k - leftSize - 1)
        val rightSubTree = result[0]!!
        val detachedTree = result[1]
        if (detachedTree == null) {
            root.right = rightSubTree.left
            root.recalculateSize()
            rightSubTree.left = null
            rightSubTree.recalculateSize()
            listOf(root, rightSubTree)
        } else {
            root.recalculateSize()
            listOf(root, detachedTree)
        }
    } else {
        // root выше справа
        // поиск в левом поддереве.
        val result = split(root!!.left, k)
        val leftSubTree = result[0]!!
        val rightSubtree = result[1]
        root.left = rightSubtree
        root.recalculateSize()
        listOf(leftSubTree, root)
    }
}

fun Node.recalculateSize() {
    size = (left?.size ?: 0) + (right?.size ?: 0) + 1
}