Python Program for BST Operations

This program implements three fundamental operations on a Binary Search Tree (BST): inserting a new node, deleting an existing node, and searching for a node. Each function is documented to explain its purpose and the approach used.

class TreeNode:
    """A node in a binary search tree."""
    def __init__(self, key):
        """
        Initialize a tree node with a key.
        
        :param key: int, the integer key of the node
        """
        self.left = None
        self.right = None
        self.val = key

class BinarySearchTree:
    """Operations on a binary search tree."""
    def __init__(self):
        """Initialize an empty BST."""
        self.root = None

    def insert(self, key):
        """
        Insert a new node with the given key in the BST.
        
        :param key: int, the key to insert
        """
        self.root = self._insert_recursive(self.root, key)

    def _insert_recursive(self, node, key):
        """
        Helper method to insert recursively based on BST properties.
        
        :param node: TreeNode, the current node in the traversal
        :param key: int, the key to insert
        :return: TreeNode, the adjusted node
        """
        if not node:
            return TreeNode(key)
        elif key < node.val:
            node.left = self._insert_recursive(node.left, key)
        else:
            node.right = self._insert_recursive(node.right, key)
        return node

    def delete(self, key):
        """
        Delete the node with the specified key from the BST.
        
        :param key: int, the key of the node to delete
        """
        self.root = self._delete_recursive(self.root, key)

    def _delete_recursive(self, node, key):
        """
        Helper method to delete a node recursively.
        
        :param node: TreeNode, the current node in the traversal
        :param key: int, the key of the node to delete
        :return: TreeNode, the adjusted node after deletion
        """
        if not node:
            return node
        if key < node.val: node.left = self._delete_recursive(node.left, key) elif key > node.val:
            node.right = self._delete_recursive(node.right, key)
        else:
            if not node.left:
                return node.right
            elif not node.right:
                return node.left
            temp_val = self._get_min(node.right)
            node.val = temp_val
            node.right = self._delete_recursive(node.right, temp_val)
        return node

    def _get_min(self, node):
        """
        Get the minimum value in the BST.
        
        :param node: TreeNode, the node from where to find the minimum
        :return: int, the minimum value found
        """
        current = node
        while current.left is not None:
            current = current.left
        return current.val

    def search(self, key):
        """
        Search for a node with the specified key in the BST.
        
        :param key: int, the key to search for
        :return: bool, True if the node is found, False otherwise
        """
        return self._search_recursive(self.root, key)

    def _search_recursive(self, node, key):
        """
        Helper method to search for a key recursively.
        
        :param node: TreeNode, the current node in the traversal
        :param key: int, the key to search for
        :return: bool, True if found, False otherwise
        """
        if not node:
            return False
        elif key == node.val:
            return True
        elif key < node.val:
            return self._search_recursive(node.left, key)
        else:
            return self._search_recursive(node.right, key)

# Example Usage
if __name__ == "__main__":
    bst = BinarySearchTree()
    bst.insert(50)
    bst.insert(30)
    bst.insert(20)
    bst.insert(40)
    bst.insert(70)
    bst.insert(60)
    bst.insert(80)
    
    print("Search for 40:", bst.search(40))
    bst.delete(70)
    print("Search for 70:", bst.search(70))

The program defines a TreeNode class to represent individual nodes of the BST and a BinarySearchTree class that encapsulates the operations. Each method in the BinarySearchTree class is accompanied by a helper function to facilitate recursive operations, ensuring that the tree’s properties are maintained throughout insertions, deletions, and searches.