How to implement a binary search tree in Python?

First, it is essential to understand the fundamental properties and operations of the Binary Search Tree (BST). A BST is a data structure where each node has at most two children, commonly referred to as the left child and the right child. In a BST, the value of the left child is less than that of its parent, and the value of the right child is greater than or equal to that of its parent. This property must be recursively maintained across all nodes in the tree.

Below is a simple Python implementation that includes the node definition and basic insertion operations:

python
class TreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

Next, we can define a Binary Search Tree class and implement basic operations such as insertion and search:

python
class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, key):
        # Create a new node
        new_node = TreeNode(key)
        
        if self.root is None:
            self.root = new_node
            return
        
        current = self.root
        while True:
            parent = current
            if key < current.val:
                current = current.left
                if current is None:
                    parent.left = new_node
                    return
            else:
                current = current.right
                if current is None:
                    parent.right = new_node
                    return

    def search(self, key):
        current = self.root
        while current:
            if key == current.val:
                return True
            elif key < current.val:
                current = current.left
            else:
                current = current.right
        return False

In the above code, we first define the TreeNode class, which contains a value and two references to its child nodes. The BinarySearchTree class includes the insert method for adding new values to the BST and the search method for finding values.

Example Usage:

Initialize the BST and insert some values:

python
bst = BinarySearchTree()
bst.insert(8)
bst.insert(3)
bst.insert(10)
bst.insert(1)
bst.insert(6)
bst.insert(14)
bst.insert(4)
bst.insert(7)

Search for a value in the tree:

python
print(bst.search(10))  # Output: True
print(bst.search(13))  # Output: False

This implementation of the BST is quite basic and can be extended with additional features as needed, such as deleting nodes, printing the tree, and validating the validity of the BST.