BST

package main

import (
    "errors"

    "golang.org/x/exp/constraints"
)

type node[K constraints.Ordered, V any] struct {
    key   K
    value V
    left  *node[K, V]
    right *node[K, V]
}

type BinarySearchTree[K constraints.Ordered, V any] struct {
    root *node[K, V]
}

func (n *node[K, V]) insert(key K, value V) {
    if key <= n.key {
        if n.left == nil {
            n.left = &node[K, V]{key, value, nil, nil}
        } else {
            n.left.insert(key, value)
        }
    } else {
        if n.right == nil {
            n.right = &node[K, V]{key, value, nil, nil}
        } else {
            n.right.insert(key, value)
        }
    }

}

func (b *BinarySearchTree[K, V]) Insert(key K, value V) {
    if b.root == nil {
        b.root = &node[K, V]{key, value, nil, nil}
    } else {
        b.root.insert(key, value)
    }
}

func (n *node[K, V]) search(key K) (V, error) {
    if n.key == key {
        return n.value, nil
    }
    var value V
    if key < n.key {
        if n.left == nil {
            return value, errors.New("not found")
        } else {
            return n.left.search(key)
        }
    } else {
        if n.right == nil {
            return value, errors.New("not found")
        } else {
            return n.right.search(key)
        }
    }
}

func (B *BinarySearchTree[K, V]) Search(key K) (V, error) {
    return B.root.search(key)
}