# 1. Introduction

A Binary Search Tree (BST) is a type of Binary Tree where the nodes are arranged based on the following properties:

- The left subtree of a node contains only nodes with values less than the node's value.

- The right subtree of a node contains only nodes with values greater than the node's value.

- The left and right subtrees are also BSTs.

BSTs are particularly useful for searching operations, as they facilitate faster look-ups compared to arrays and linked lists.

# 2. Implementation Steps

1. Define a Node structure with fields for data, left, and right.

2. Implement methods for insertion (Insert), searching (Search), and in-order traversal (InOrder).

3. Enhance the tree with a method to delete a node (Delete).

# 3. Implementation in Golang

``````package main
import (
"fmt"
)
type Node struct {
data  int
left  *Node
right *Node
}
// Insert a value into the BST
func (n *Node) Insert(value int) {
if value <= n.data {
if n.left == nil {
n.left = &Node{data: value}
} else {
n.left.Insert(value)
}
} else {
if n.right == nil {
n.right = &Node{data: value}
} else {
n.right.Insert(value)
}
}
}
// Search for a value in the BST
func (n *Node) Search(value int) bool {
if n == nil {
return false
}
if value == n.data {
return true
}
if value < n.data {
return n.left.Search(value)
}
return n.right.Search(value)
}
// InOrder traversal of the BST
func (n *Node) InOrder() {
if n != nil {
n.left.InOrder()
fmt.Print(n.data, " ")
n.right.InOrder()
}
}
func main() {
root := &Node{data: 50}
root.Insert(30)
root.Insert(70)
root.Insert(20)
root.Insert(40)
root.Insert(60)
root.Insert(80)
fmt.Print("InOrder Traversal: ")
root.InOrder()
fmt.Println("\nSearch for 25:", root.Search(25))
fmt.Println("Search for 60:", root.Search(60))
}
``````

### Output:

```InOrder Traversal: 20 30 40 50 60 70 80
Search for 25: false
Search for 60: true
```

### Explanation:

1. The Node struct is the foundation of the BST. It consists of the data, left, and right pointers.

2. The Insert method adds a new value into the BST by recursively finding the correct position.

3. The Search method checks for the presence of a value in the BST. It traverses the tree based on the value it's looking for, making the search operation efficient.

4. The InOrder method provides an in-order traversal of the BST which results in a sorted output of the tree's values.

5. In the main function, after inserting nodes into the tree, we demonstrate an in-order traversal and perform a couple of search operations.

This Binary Search Tree forms the foundation for many advanced operations like balancing and finding predecessors or successors of a node.