This program demonstrates how to perform the three fundamental operations—insert, delete, and search—in a Binary Search Tree using the Go programming language. These operations are essential for maintaining and utilizing BSTs efficiently.

Program Explanation

The program uses a simple struct to define a BST node, each containing integer values and pointers to left and right child nodes. Each operation is implemented as a function:

Code Structure

1. TreeNode struct: Defines the structure of the BST nodes.
2. Insert function: Inserts a new node with the given value into the BST.
3. Delete function: Removes a node with the specified value from the BST.
4. Search function: Searches for a node with a given value in the BST.

Code with Documentation

package main

import (
    "fmt"
)

// TreeNode defines a binary search tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// Insert inserts a new node with the given value into the BST.
func (node *TreeNode) Insert(val int) *TreeNode {
    if node == nil {
        return &TreeNode{Val: val}
    }
    if val < node.Val {
        node.Left = node.Left.Insert(val)
    } else {
        node.Right = node.Right.Insert(val)
    }
    return node
}

// Delete removes a node with the specified value from the BST.
func (node *TreeNode) Delete(val int) *TreeNode {
    if node == nil {
        return nil
    }
    if val < node.Val {
        node.Left = node.Left.Delete(val)
    } else if val > node.Val {
        node.Right = node.Right.Delete(val)
    } else {
        if node.Left == nil {
            return node.Right
        } else if node.Right == nil {
            return node.Left
        }
        node.Val = node.Right.minValue()
        node.Right = node.Right.Delete(node.Val)
    }
    return node
}

// minValue returns the minimum value found in the BST.
func (node *TreeNode) minValue() int {
    current := node
    for current.Left != nil {
        current = current.Left
    }
    return current.Val
}

// Search searches for a node with a given value.
func (node *TreeNode) Search(val int) *TreeNode {
    if node == nil || node.Val == val {
        return node
    }
    if val < node.Val {
        return node.Left.Search(val)
    }
    return node.Right.Search(val)
}

func main() {
    root := &TreeNode{Val: 20}
    root.Insert(10)
    root.Insert(30)
    root.Insert(5)
    root.Insert(15)
    
    fmt.Println("Search for 10:", root.Search(10) != nil)
    root.Delete(10)
    fmt.Println("Search for 10 after deletion:", root.Search(10) != nil)
}

Conclusion

The provided Go code enables efficient management of a BST through insertions, deletions, and searches, illustrating the dynamic nature of BSTs. This setup ensures optimal performance for operations that involve ordered data, making BSTs suitable for a variety of applications, from database management to memory allocation.