Дано бинарное дерево поиска, в котором хранятся ключи. Ключи — уникальные целые числа. Найдите вершину с заданным ключом и удалите её из дерева так, чтобы дерево осталось корректным бинарным деревом поиска. Если ключа в дереве нет, то изменять дерево не надо. На вход вашей функции подаётся корень дерева и ключ, который надо удалить. Функция должна вернуть корень изменённого дерева. Сложность удаления узла должна составлять O(h), где h — высота дерева.

Создавать новые вершины (вдруг очень захочется) нельзя.

Ключи дерева – натуральные числа, не превышающие 10⁹. В итоговом решении не надо определять свою структуру/свой класс, описывающий вершину дерева. Мы рекомендуем воспользоваться заготовками кода для данной задачи

По умолчанию выбран компилятор Make. Решение нужно отправлять в виде файла с расширением, которое соответствует вашему языку программирования. Если вы пишете на Java, имя файла должно быть Solution.java, для C# – Solution.cs. Для остальных языков назовите файл my_solution.ext, заменив ext на необходимое расширение. Ниже приведены сигнатуры функций, которые надо реализовать.

Go

package main

// Node do not declare Node in your submit-file 
type Node struct {
	value    int
	left   *Node
	right  *Node
}

func remove(node *Node, key int) *Node {
	// your solution
}