Binary Search Tree (BST)

A Binary Search Tree (BST) is a specialized binary tree data structure that maintains sorted data and allows fast insertion, deletion, and search operations.

Properties of BST

• Each node has at most two children: left and right.
• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both left and right subtrees must also be BSTs.

Basic Operations

Insertion

Insert a new key by traversing the tree and placing it at the correct position to maintain BST properties.

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

Search

Search a key by traversing either to the left or the right subtree depending on the comparison with the current node’s key.

def search(node, key):
    if node is None or node.key == key:
        return node
    if key < node.key:
        return search(node.left, key)
    else:
        return search(node.right, key)

Deletion

Delete a node while maintaining BST properties:

• If the node has no children, remove it directly.
• If the node has one child, replace it with that child.
• If the node has two children, replace its value with its in-order successor's value and delete the successor.

def minValueNode(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

def deleteNode(root, key):
    if root is None:
        return root
    if key < root.key:
        root.left = deleteNode(root.left, key)
    elif key > root.key:
        root.right = deleteNode(root.right, key)
    else:
        # Node with one or no child
        if root.left is None:
            temp = root.right
            root = None
            return temp
        elif root.right is None:
            temp = root.left
            root = None
            return temp
        
        # Node with two children
        temp = minValueNode(root.right)
        root.key = temp.key
        root.right = deleteNode(root.right, temp.key)
    return root

Inorder Traversal (Sorted Order)

def inorder(root):
    if root is not None:
        inorder(root.left)
        print(root.key, end=" -> ")
        inorder(root.right)

Node Definition

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