Дано бинарное дерево поиска, в котором хранятся ключи. Ключи — уникальные целые числа. Найдите вершину с заданным ключом и удалите её из дерева так, чтобы дерево осталось корректным бинарным деревом поиска. Если ключа в дереве нет, то изменять дерево не надо. На вход вашей функции подаётся корень дерева и ключ, который надо удалить. Функция должна вернуть корень изменённого дерева. Сложность удаления узла должна составлять O(h), где h — высота дерева.
Создавать новые вершины (вдруг очень захочется) нельзя.
Ключи дерева – натуральные числа, не превышающие 109. В итоговом решении не надо определять свою структуру/свой класс, описывающий вершину дерева. Мы рекомендуем воспользоваться заготовками кода для данной задачи
По умолчанию выбран компилятор 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
}