Binary Search Tree (BST) Implementation with CRUD Operations

package main

import (
	"fmt"
	"sync"
)

// Ordered is a minimal ordered constraint (no extra deps).
// It allows using < and > on the type parameter.
type Ordered interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 |
		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
		~float32 | ~float64 |
		~string
}

// BST is a thread-safe Binary Search Tree supporting duplicates.
type BST[T Ordered] struct {
	mu   sync.RWMutex
	root *node[T]
}

type node[T Ordered] struct {
	value T
	count int
	left  *node[T]
	right *node[T]
}

func NewBST[T Ordered]() *BST[T] { return &BST[T]{} }

func (b *BST[T]) Insert(value T) {
	b.mu.Lock()
	defer b.mu.Unlock()
	b.root = insertNode(b.root, value)
}

func insertNode[T Ordered](n *node[T], value T) *node[T] {
	if n == nil {
		return &node[T]{value: value, count: 1}
	}
	if value < n.value {
		n.left = insertNode(n.left, value)
		return n
	}
	if value > n.value {
		n.right = insertNode(n.right, value)
		return n
	}
	n.count++
	return n
}

func (b *BST[T]) Search(value T) bool {
	b.mu.RLock()
	defer b.mu.RUnlock()
	cur := b.root
	for cur != nil {
		if value < cur.value {
			cur = cur.left
			continue
		}
		if value > cur.value {
			cur = cur.right
			continue
		}
		return true
	}
	return false
}

// Delete removes a single occurrence of value. Returns true if something was removed.
func (b *BST[T]) Delete(value T) bool {
	b.mu.Lock()
	defer b.mu.Unlock()
	var deleted bool
	b.root, deleted = deleteNode(b.root, value)
	return deleted
}

func deleteNode[T Ordered](n *node[T], value T) (*node[T], bool) {
	if n == nil {
		return nil, false
	}
	if value < n.value {
		var deleted bool
		n.left, deleted = deleteNode(n.left, value)
		return n, deleted
	}
	if value > n.value {
		var deleted bool
		n.right, deleted = deleteNode(n.right, value)
		return n, deleted
	}

	// value == n.value
	if n.count > 1 {
		n.count--
		return n, true
	}

	// Node with 0 or 1 child
	if n.left == nil {
		return n.right, true
	}
	if n.right == nil {
		return n.left, true
	}

	// Node with 2 children: replace with inorder successor (min of right subtree)
	succ := n.right
	for succ.left != nil {
		succ = succ.left
	}
	n.value = succ.value
	n.count = succ.count
	// Delete successor node entirely (all its duplicates moved here)
	n.right = deleteAll(n.right, succ.value)
	return n, true
}

func deleteAll[T Ordered](n *node[T], value T) *node[T] {
	if n == nil {
		return nil
	}
	if value < n.value {
		n.left = deleteAll(n.left, value)
		return n
	}
	if value > n.value {
		n.right = deleteAll(n.right, value)
		return n
	}
	// remove this node completely
	if n.left == nil {
		return n.right
	}
	if n.right == nil {
		return n.left
	}
	succ := n.right
	for succ.left != nil {
		succ = succ.left
	}
	n.value = succ.value
	n.count = succ.count
	n.right = deleteAll(n.right, succ.value)
	return n
}

func (b *BST[T]) InOrder() []T {
	b.mu.RLock()
	defer b.mu.RUnlock()
	var out []T
	inOrder(b.root, &out)
	return out
}

func inOrder[T Ordered](n *node[T], out *[]T) {
	if n == nil {
		return
	}
	inOrder(n.left, out)
	for i := 0; i < n.count; i++ {
		*out = append(*out, n.value)
	}
	inOrder(n.right, out)
}

func (b *BST[T]) PreOrder() []T {
	b.mu.RLock()
	defer b.mu.RUnlock()
	var out []T
	preOrder(b.root, &out)
	return out
}

func preOrder[T Ordered](n *node[T], out *[]T) {
	if n == nil {
		return
	}
	for i := 0; i < n.count; i++ {
		*out = append(*out, n.value)
	}
	preOrder(n.left, out)
	preOrder(n.right, out)
}

func (b *BST[T]) PostOrder() []T {
	b.mu.RLock()
	defer b.mu.RUnlock()
	var out []T
	postOrder(b.root, &out)
	return out
}

func postOrder[T Ordered](n *node[T], out *[]T) {
	if n == nil {
		return
	}
	postOrder(n.left, out)
	postOrder(n.right, out)
	for i := 0; i < n.count; i++ {
		*out = append(*out, n.value)
	}
}

// Height returns the tree height (empty tree = 0).
func (b *BST[T]) Height() int {
	b.mu.RLock()
	defer b.mu.RUnlock()
	return height(b.root)
}

func height[T Ordered](n *node[T]) int {
	if n == nil {
		return 0
	}
	lh := height(n.left)
	rh := height(n.right)
	if lh > rh {
		return lh + 1
	}
	return rh + 1
}

func main() {
	bst := NewBST[int]()
	for _, v := range []int{5, 3, 7, 1, 4, 6, 8, 7, 7} {
		bst.Insert(v)
	}

	fmt.Println("search 4:", bst.Search(4))
	fmt.Println("height:", bst.Height())
	fmt.Println("in-order:", bst.InOrder())
	fmt.Println("pre-order:", bst.PreOrder())
	fmt.Println("post-order:", bst.PostOrder())

	bst.Delete(7)
	fmt.Println("after delete one 7:", bst.InOrder())
	bst.Delete(7)
	bst.Delete(7)
	fmt.Println("after delete all 7s:", bst.InOrder())
}