N

N. Разбиение дерева

Дано бинарное дерево поиска, в котором хранятся целые числа. От этого дерева надо отделить k самых маленьких элементов.

Реализуйте функцию, которая принимает корень дерева и число k , а возвращает два BST — в первом k наименьших элементов из исходного дерева, а во втором — оставшиеся вершины BST.

В вершинах дерева уже записаны корректные размеры поддеревьев (точное название поля смотрите в заготовках кода). После разбиения размеры должны остаться корректными — вам придётся пересчитывать их на ходу.

Ваше решение должно иметь асимптотику O(h), где h — высота исходного дерева.

По умолчанию выбран компилятор make.

Шаблон для Go:

package main

/**
Comment it before submitting
type Node struct {
	value    int
	left   *Node
	right  *Node
	size     int
}
**/

func split(node *Node, k int) (*Node, *Node) {
	// Your code
	// “ヽ(´▽｀)ノ”
}

Формат ввода

Числа, записанные в вершинах дерева, лежат в диапазоне от 0 до 10⁹. Дерево не содержит одинаковых ключей. Число вершин в дереве не превосходит 10⁵.