Implement binary search tree insertion deletion search in Python

Here's an implementation of a Binary Search Tree (BST) in Python with basic operations such as insertion, deletion, and search:

class TreeNode:

    def __init__(self, key):

        self.left = None

        self.right = None

        self.val = key

class BinarySearchTree:

    def __init__(self):

        self.root = None

    def insert(self, key):

        if self.root is None:

            self.root = TreeNode(key)

        else:

            self._insert_recursive(self.root, key)

    def _insert_recursive(self, root, key):

        if key < root.val:

            if root.left is None:

                root.left = TreeNode(key)

            else:

                self._insert_recursive(root.left, key)

        else:

            if root.right is None:

                root.right = TreeNode(key)

            else:

                self._insert_recursive(root.right, key)

    def delete(self, key):

        self.root = self._delete_recursive(self.root, key)

    def _delete_recursive(self, root, key):

        if root is None:

            return root

        if key < root.val:

            root.left = self._delete_recursive(root.left, key)

        elif key > root.val:

            root.right = self._delete_recursive(root.right, key)

        else:

            # Case 1: Node to be deleted has no children (leaf node)

            if root.left is None and root.right is None:

                return None

            # Case 2: Node to be deleted has only one child

            elif root.left is None:

                return root.right

            elif root.right is None:

                return root.left

            # Case 3: Node to be deleted has two children

            else:

                # Find the minimum value node in the right subtree

                min_node = self._find_min(root.right)

                # Replace the current node value with the min_node value

                root.val = min_node.val

                # Delete the min_node from the right subtree

                root.right = self._delete_recursive(root.right, min_node.val)

        return root

    def _find_min(self, node):

        current = node

        while current.left is not None:

            current = current.left

        return current

    def search(self, key):

        return self._search_recursive(self.root, key)

    def _search_recursive(self, root, key):

        if root is None or root.val == key:

            return root

        if key < root.val:

            return self._search_recursive(root.left, key)

        else:

            return self._search_recursive(root.right, key)

# Example usage:

if __name__ == '__main__':

    bst = BinarySearchTree()

    # Insert elements

    bst.insert(50)

    bst.insert(30)

    bst.insert(20)

    bst.insert(40)

    bst.insert(70)

    bst.insert(60)

    bst.insert(80)

    # Search for an element

    key = 40

    if bst.search(key):

        print(f"{key} found in the BST.")

    else:

        print(f"{key} not found in the BST.")

    # Delete an element

    bst.delete(20)

    # Search for an element after deletion

    key = 20

    if bst.search(key):

        print(f"{key} found in the BST.")

    else:

        print(f"{key} not found in the BST.")

Explanation:

1. TreeNode Class (TreeNode):

   • Represents a single node in the binary search tree with attributes left, right, and val (or key).

2. BinarySearchTree Class (BinarySearchTree):

   • Initializes with root set to None.

3. Insertion (insert method):

   • Inserts a new node with key into the BST. If the tree is empty (self.root is None), it sets self.root to the new node. Otherwise, it recursively finds the correct position to insert the new node based on BST properties (left child < parent < right child).

4. Deletion (delete method):

   • Deletes a node with key from the BST. Uses a recursive approach to find the node to be deleted and handles three cases:
     • Node has no children (leaf node).
     • Node has one child.
     • Node has two children (finds the minimum node in the right subtree, replaces the node's value with this min node's value, and deletes the min node from the right subtree).

5. Find Minimum Node (_find_min method):

   • Helper function to find the node with the minimum value in a given subtree.

6. Search (search method):

   • Searches for a node with key in the BST. Returns the node if found, None otherwise.

7. Example Usage:

   • Demonstrates how to create a BST, insert elements, search for an element, and delete an element.

This implementation provides basic functionalities required for a binary search tree in Python. Adjustments can be made based on specific requirements or additional operations needed for the BST.