Data Structures and Algorithms: How to Implement and Use Binary Search Tree in Python

A binary search tree is a type of data structure that stores elements in a hierarchical order. It allows fast and efficient searching, sorting, and insertion of elements. A binary search tree has the following properties:

Each node has a value and at most two children: left and right.
The value of the left child is always less than the value of the parent node.
The value of the right child is always greater than the value of the parent node.
The left and right subtrees of each node are also binary search trees.

It is called a search tree because it can be used to search for the presence of a number in O(log(n)) time.

In Python, you can implement a binary search tree using a class that represents a node. Each node has a value, a left child, and a right child. You can also define methods to insert, search, and traverse the tree.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        self.root = self._insert(self.root, value)

    def _insert(self, root, value):
        if root is None:
            return Node(value)
        if value < root.value:
            root.left = self._insert(root.left, value)
        elif value > root.value:
            root.right = self._insert(root.right, value)
        return root

    def search(self, value):
        return self._search(self.root, value)

    def _search(self, root, value):
        if root is None or root.value == value:
            return root
        if value < root.value:
            return self._search(root.left, value)
        return self._search(root.right, value)

To use this class, you can create an instance of it and call its methods. For example, you can create a binary search tree with the following values: 10, 5, 15, 3, 7, 12, 18. Then, you can search for the value 7 and print the tree in order. The output would be:

# Create a binary search tree
bst = BinarySearchTree()

# Insert values into the tree
values_to_insert = [10, 5, 15, 3, 7, 12, 18]
for value in values_to_insert:
    bst.insert(value)

# Search for values in the tree
search_values = [7, 20]
for value in search_values:
    result = bst.search(value)
    if result:
        print(f"Value {value} found in the tree.")
    else:
        print(f"Value {value} not found in the tree.")