# 1. Introduction

A Binary Search Tree (BST) is a binary tree where each node has a comparable value, and the left subtree of a node contains only nodes with values less than the node's value, while the right subtree only nodes with values greater than the node's value. This provides an efficient way of inserting, looking up, and deleting items, as each decision cuts down the possibilities in half (similar to binary search).

# 2. Implementation Steps

1. Define a Node class with attributes value, left, and right.

2. Initialize a BinarySearchTree class with a root node.

3. Implement the insert method to add nodes in accordance with BST properties.

4. Implement a search method to find a value in the BST.

5. Implement the delete method to remove nodes from the BST.

6. Implement a display method to print the tree in an in-order traversal.

# 3. Implementation in Ruby Programming

``````class Node
attr_accessor :value, :left, :right
def initialize(value)
@value = value
@left = nil
@right = nil
end
end
class BinarySearchTree
def initialize
@root = nil
end
# Insert value into the BST
def insert(value)
@root = insert_recursive(@root, value)
end
# Search for a value in the BST
def search(value)
search_recursive(@root, value)
end
# Delete a value from the BST
def delete(value)
@root = delete_recursive(@root, value)
end
# Display BST in in-order traversal
def display
display_recursive(@root)
end
private
def insert_recursive(node, value)
return Node.new(value) if node.nil?
if value < node.value
node.left = insert_recursive(node.left, value)
elsif value > node.value
node.right = insert_recursive(node.right, value)
end
node
end
def search_recursive(node, value)
return false if node.nil?
return true if node.value == value
value < node.value ? search_recursive(node.left, value) : search_recursive(node.right, value)
end
def delete_recursive(node, value)
return nil if node.nil?
if value < node.value
node.left = delete_recursive(node.left, value)
elsif value > node.value
node.right = delete_recursive(node.right, value)
else
return node.right if node.left.nil?
return node.left if node.right.nil?
min_larger_node = find_min(node.right)
node.value = min_larger_node.value
node.right = delete_recursive(node.right, min_larger_node.value)
end
node
end
def find_min(node)
current = node
current = current.left while current.left
current
end
def display_recursive(node)
return if node.nil?
display_recursive(node.left)
puts node.value
display_recursive(node.right)
end
end
# Client code
bst = BinarySearchTree.new
[50, 30, 70, 20, 40, 60, 80].each { |i| bst.insert(i) }
puts "In-order traversal of BST:"
bst.display
puts "Searching for 25 in BST: #{bst.search(25)}"
puts "Searching for 70 in BST: #{bst.search(70)}"
bst.delete(70)
puts "After deleting 70, in-order traversal:"
bst.display
``````

### Output:

```In-order traversal of BST:
20
30
40
50
60
70
80
Searching for 25 in BST: false
Searching for 70 in BST: true
After deleting 70, in-order traversal:
20
30
40
50
60
80
```

### Explanation:

1. The Node class represents each element in the BST. Each node has a value, a left child, and a right child.

2. The BinarySearchTree class initializes with a root node set to nil.

3. The insert method adds a value to the tree according to BST properties.

4. The search method looks for a value in the BST and returns a boolean.

5. The delete method removes a node with a given value from the BST.

6. The private helper functions facilitate various BST operations, including insert_recursive, search_recursive, delete_recursive, and display_recursive. The find_min function retrieves the smallest node from the right subtree, used during node deletion.

7. The client code demonstrates insertion, display, search, and deletion operations on the BST.