Creating a Binary Search Tree (BST)

Introduction to Binary Search Trees

"A Binary Search Tree represents a powerful data structure that combines the efficiency of binary search with the flexibility of a linked structure."

A Binary Search Tree (BST) is a special type of binary tree where each node follows specific ordering properties. The left subtree of any node contains only values less than the node's value, while the right subtree contains only values greater than the node's value. This property must be maintained throughout the entire tree.

Key Properties of BST

• All nodes in the left subtree have values less than the current node
• All nodes in the right subtree have values greater than the current node
• Both left and right subtrees must also be binary search trees
• The tree structure provides an average time complexity of O(log n) for operations

Node Implementation

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

Tree Implementation

class BST:
    def __init__(self):
        self.root = None

    def insert(self, root, key):
        if root is None:
            return Node(key)
        
        if key < root.value:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)
        
        return root

    def insert_value(self, key):
        if not self.root:
            self.root = Node(key)
        else:
            self.insert(self.root, key)

Tree Traversal Methods

BSTs can be traversed in three main ways:

# Pre-order Traversal
def pre_order_traversal(root):
    if root:
        print(root.value, end=" ")
        pre_order_traversal(root.left)
        pre_order_traversal(root.right)

# In-order Traversal
def in_order_traversal(root):
    if root:
        in_order_traversal(root.left)
        print(root.value, end=" ")
        in_order_traversal(root.right)

# Post-order Traversal
def post_order_traversal(root):
    if root:
        post_order_traversal(root.left)
        post_order_traversal(root.right)
        print(root.value, end=" ")

Complete BST Implementation with Insertion and Deletion

Let's explore the complete implementation of a Binary Search Tree with insertion and deletion operations. This implementation handles all cases of deletion and provides a clean, reusable interface.

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

class BST:
    def __init__(self):
        self.root = None

    def insert(self, value):
        """Insert a new value into the BST"""
        if not self.root:
            self.root = Node(value)
        else:
            self._insert_recursive(self.root, value)

    def _insert_recursive(self, node, value):
        """Helper method for insertion"""
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert_recursive(node.left, value)
        else:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert_recursive(node.right, value)

    def delete(self, value):
        """Delete a value from the BST"""
        self.root = self._delete_recursive(self.root, value)

    def _delete_recursive(self, node, value):
        """Helper method for deletion"""
        # Base case: if node is None, tree is empty
        if node is None:
            return node

        # Recursively find the node to delete
        if value < node.value:
            node.left = self._delete_recursive(node.left, value)
        elif value > node.value:
            node.right = self._delete_recursive(node.right, value)
        else:
            # Node found! Handle the three deletion cases

            # Case 1: Leaf node (no children)
            if node.left is None and node.right is None:
                return None

            # Case 2: Node with one child
            if node.left is None:
                return node.right
            if node.right is None:
                return node.left

            # Case 3: Node with two children
            # Find the inorder successor (smallest value in right subtree)
            successor = self._find_min(node.right)
            # Copy successor value to current node
            node.value = successor.value
            # Delete the successor
            node.right = self._delete_recursive(node.right, successor.value)

        return node

    def _find_min(self, node):
        """Helper method to find the minimum value node in a subtree"""
        current = node
        while current.left is not None:
            current = current.left
        return current

Understanding the Delete Operation

The delete operation handles three cases:

• Deleting a leaf node: Simply remove the node
• Deleting a node with one child: Replace node with its child
• Deleting a node with two children: Replace with inorder successor

Example Usage

# Create a BST and insert values
bst = BST()
values = [50, 30, 20, 40, 70, 60, 80]
for value in values:
    bst.insert(value)

# Delete operations
bst.delete(20)  # Deleting leaf node
bst.delete(30)  # Deleting node with one child
bst.delete(70)  # Deleting node with two children

Node Deletion Cases

When deleting a node from a BST, we need to handle three distinct cases:

1. Leaf Node (No Children): Simply remove the node from the tree.
2. One Child: Replace the node with its child.
3. Two Children: Replace with the inorder successor (smallest value in right subtree), then delete the successor.

Usage Example

Here's how you can use this implementation:

# Create a new BST
bst = BST()

# Insert some values
values = [50, 30, 20, 40, 70, 60, 80]
for value in values:
    bst.insert(value)

# Delete a leaf node
bst.delete(20)

# Delete a node with one child
bst.delete(30)

# Delete a node with two children
bst.delete(70)