J

J. Добавь узел

Дано BST. Надо вставить узел с заданным ключом. Ключи в дереве могут повторяться.

На вход функции подаётся корень корректного бинарного дерева поиска и ключ, который надо вставить в дерево. Осуществите вставку этого ключа. Если ключ уже есть в дереве, то его дубликаты уходят в правого сына. Таким образом вид дерева после вставки определяется однозначно. Функция должна вернуть корень дерева после вставки вершины.

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

Формат ввода

Ключи дерева – натуральные числа, не превосходящие 10⁹. Число вершин в дереве не превосходит 10⁵.

**Замечания про отправку решений **

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

Шаблон для Go:

package main

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

func insert(root *Node, key int) *Node {
	// Your code
	// “ヽ(´▽｀)ノ”
}