Бинарное дерево поиска

type TreeNode[T any] struct {
    Key   int
    Value T
    Left  *TreeNode[T]
    Right *TreeNode[T]
}

func insert[T any](root *TreeNode[T], key int, val T) *TreeNode[T] {
    if root == nil { return &TreeNode[T]{Key: key, Value: val} }
    if key < root.Key      { root.Left  = insert(root.Left,  key, val) }
    else if key > root.Key { root.Right = insert(root.Right, key, val) }
    else                   { root.Value = val } // обновление
    return root
}

func search[T any](root *TreeNode[T], key int) (T, bool) {
    if root == nil         { var z T; return z, false }
    if key == root.Key     { return root.Value, true }
    if key < root.Key      { return search(root.Left,  key) }
    return search(root.Right, key)
}

func delete[T any](root *TreeNode[T], key int) *TreeNode[T] {
    if root == nil { return nil }
    if key < root.Key      { root.Left  = delete(root.Left,  key) }
    else if key > root.Key { root.Right = delete(root.Right, key) }
    else {
        if root.Left == nil  { return root.Right }
        if root.Right == nil { return root.Left }
        min := findMin(root.Right)
        root.Key, root.Value = min.Key, min.Value
        root.Right = delete(root.Right, min.Key)
    }
    return root
}

func findMin[T any](n *TreeNode[T]) *TreeNode[T] {
    for n.Left != nil { n = n.Left }
    return n
}