BST Insertion, Deletion, and Search Operations

Key Insights

BST operations rely on a simple invariant: left children are smaller, right children are larger—this property enables O(log n) average-case performance for search, insert, and delete operations.
Deletion is the trickiest operation because removing a node with two children requires finding an in-order successor or predecessor to maintain the BST property.
Unbalanced BSTs degrade to O(n) performance; understanding these fundamentals is essential before moving to self-balancing trees like AVL or Red-Black trees.

Introduction to Binary Search Trees

Binary Search Trees are the workhorse data structure for ordered data. They provide efficient search, insertion, and deletion by maintaining a simple invariant: for any node, all values in its left subtree are smaller, and all values in its right subtree are larger.

This property gives us O(log n) average-case time complexity for core operations. However, BSTs have a weakness—they can become unbalanced, degrading to O(n) in the worst case. Understanding vanilla BST operations is foundational before tackling self-balancing variants.

Let’s build a complete BST implementation from scratch, examining each operation in detail.

BST Node Structure and Setup

Every BST starts with a node definition. Each node holds a value and pointers to left and right children.

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


class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def is_empty(self):
        return self.root is None

The tree itself just maintains a reference to the root node. An empty tree has root = None. This simplicity is deceptive—the real complexity lives in maintaining the BST property during modifications.

Here’s the equivalent in JavaScript:

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null;
    }
    
    isEmpty() {
        return this.root === null;
    }
}

Search Operation

Search is the simplest operation and demonstrates the core BST traversal pattern. Starting at the root, compare the target value with the current node:

If equal, we found it
If smaller, go left
If larger, go right
If we hit null, the value doesn’t exist

Here’s the recursive implementation:

def search_recursive(self, value):
    return self._search_recursive(self.root, value)

def _search_recursive(self, node, value):
    # Base cases: not found or found
    if node is None:
        return None
    if node.value == value:
        return node
    
    # Recursive cases: go left or right
    if value < node.value:
        return self._search_recursive(node.left, value)
    else:
        return self._search_recursive(node.right, value)

The iterative version avoids recursion overhead and is often preferred in production:

def search_iterative(self, value):
    current = self.root
    
    while current is not None:
        if value == current.value:
            return current
        elif value < current.value:
            current = current.left
        else:
            current = current.right
    
    return None

The iterative approach is straightforward: maintain a pointer and update it based on comparisons until you find the value or exhaust the tree. Both approaches have O(h) time complexity where h is the tree height.

Insertion Operation

Insertion follows the same traversal pattern as search. We navigate to where the value should be, then add it there. The key insight: every new node becomes a leaf.

def insert(self, value):
    if self.root is None:
        self.root = TreeNode(value)
        return
    
    self._insert_recursive(self.root, value)

def _insert_recursive(self, node, value):
    # Decide which subtree to explore
    if value < node.value:
        if node.left is None:
            # Found the spot—insert here
            node.left = TreeNode(value)
        else:
            # Keep searching in left subtree
            self._insert_recursive(node.left, value)
    elif value > node.value:
        if node.right is None:
            # Found the spot—insert here
            node.right = TreeNode(value)
        else:
            # Keep searching in right subtree
            self._insert_recursive(node.right, value)
    # If value == node.value, we ignore duplicates

This implementation ignores duplicates. Alternative strategies include:

Allow duplicates in the right subtree (or left—pick one consistently)
Maintain a count field in each node
Raise an exception

Here’s an iterative version that returns a boolean indicating success:

def insert_iterative(self, value):
    new_node = TreeNode(value)
    
    if self.root is None:
        self.root = new_node
        return True
    
    current = self.root
    while True:
        if value < current.value:
            if current.left is None:
                current.left = new_node
                return True
            current = current.left
        elif value > current.value:
            if current.right is None:
                current.right = new_node
                return True
            current = current.right
        else:
            # Duplicate found
            return False

Consider inserting values 50, 30, 70, 20, 40 in order:

Insert 50:     50

Insert 30:     50
              /
             30

Insert 70:     50
              /  \
             30   70

Insert 20:     50
              /  \
             30   70
            /
           20

Insert 40:     50
              /  \
             30   70
            /  \
           20   40

Each insertion finds its natural position based on comparisons, maintaining the BST property.

Deletion Operation

Deletion is where BSTs get interesting. We must handle three distinct cases:

Case 1: Leaf node (no children) Simply remove the node by setting the parent’s pointer to null.

Case 2: One child Replace the node with its child. The child takes over the deleted node’s position.

Case 3: Two children This is the tricky one. We can’t just remove the node—we need to find a replacement that maintains the BST property. The solution: use the in-order successor (smallest value in right subtree) or in-order predecessor (largest value in left subtree).

def delete(self, value):
    self.root = self._delete_recursive(self.root, value)

def _delete_recursive(self, node, value):
    # Base case: value not found
    if node is None:
        return None
    
    # Navigate to 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:
        # Found the node to delete
        
        # Case 1 & 2: No left child (includes leaf nodes)
        if node.left is None:
            return node.right
        
        # Case 2: No right child
        if node.right is None:
            return node.left
        
        # Case 3: Two children
        # Find in-order successor (minimum in right subtree)
        successor = self._find_minimum(node.right)
        
        # Copy successor's value to this node
        node.value = successor.value
        
        # Delete the successor from right subtree
        node.right = self._delete_recursive(node.right, successor.value)
    
    return node

def _find_minimum(self, node):
    """Find the leftmost (minimum) node in a subtree."""
    current = node
    while current.left is not None:
        current = current.left
    return current

The two-children case works by finding the in-order successor, copying its value to the node being deleted, then recursively deleting the successor (which will have at most one child, making it an easier case).

Why does the in-order successor work? It’s the smallest value larger than the deleted node, so it satisfies the BST property for both subtrees.

Time and Space Complexity Analysis

Operation	Average Case	Worst Case
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Space	O(n)	O(n)

The worst case occurs when the tree becomes a linked list—inserting sorted data creates this scenario:

Insert 1, 2, 3, 4, 5:

1
 \
  2
   \
    3
     \
      4
       \
        5

Every operation now requires traversing n nodes. This is why self-balancing trees exist:

AVL Trees: Strictly balanced, faster lookups, slower insertions
Red-Black Trees: Loosely balanced, good all-around performance
B-Trees: Optimized for disk access, used in databases

For in-memory use with random insertions, vanilla BSTs often perform well enough. When you need guaranteed O(log n) performance, reach for a balanced variant.

Practical Applications and Testing

BSTs power many real-world systems:

Database indexes: B-Trees (a BST generalization) enable fast record lookups
Symbol tables: Compilers use BSTs to store variable names and scopes
Priority queues: When you need ordered iteration alongside priority operations
Autocomplete systems: Prefix trees (tries) are BST cousins

Here’s a complete implementation with test cases:

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


class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, value):
        if self.root is None:
            self.root = TreeNode(value)
            return True
        return self._insert(self.root, value)
    
    def _insert(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = TreeNode(value)
                return True
            return self._insert(node.left, value)
        elif value > node.value:
            if node.right is None:
                node.right = TreeNode(value)
                return True
            return self._insert(node.right, value)
        return False  # Duplicate
    
    def search(self, value):
        return self._search(self.root, value)
    
    def _search(self, node, value):
        if node is None:
            return None
        if value == node.value:
            return node
        if value < node.value:
            return self._search(node.left, value)
        return self._search(node.right, value)
    
    def delete(self, value):
        self.root = self._delete(self.root, value)
    
    def _delete(self, node, value):
        if node is None:
            return None
        if value < node.value:
            node.left = self._delete(node.left, value)
        elif value > node.value:
            node.right = self._delete(node.right, value)
        else:
            if node.left is None:
                return node.right
            if node.right is None:
                return node.left
            successor = self._find_min(node.right)
            node.value = successor.value
            node.right = self._delete(node.right, successor.value)
        return node
    
    def _find_min(self, node):
        while node.left:
            node = node.left
        return node
    
    def inorder(self):
        """Returns sorted list of all values."""
        result = []
        self._inorder(self.root, result)
        return result
    
    def _inorder(self, node, result):
        if node:
            self._inorder(node.left, result)
            result.append(node.value)
            self._inorder(node.right, result)


# Test the implementation
if __name__ == "__main__":
    bst = BinarySearchTree()
    
    # Test insertions
    values = [50, 30, 70, 20, 40, 60, 80]
    for v in values:
        bst.insert(v)
    
    print(f"Inorder traversal: {bst.inorder()}")
    # Output: [20, 30, 40, 50, 60, 70, 80]
    
    # Test search
    assert bst.search(40) is not None
    assert bst.search(100) is None
    print("Search tests passed")
    
    # Test deletion - leaf node
    bst.delete(20)
    assert bst.search(20) is None
    print(f"After deleting 20: {bst.inorder()}")
    
    # Test deletion - one child
    bst.delete(30)
    print(f"After deleting 30: {bst.inorder()}")
    
    # Test deletion - two children
    bst.delete(50)
    print(f"After deleting 50 (root): {bst.inorder()}")
    
    print("All tests passed!")

Master these operations, and you’ll have the foundation for understanding more sophisticated tree structures. The patterns here—recursive traversal, maintaining invariants during modification, handling edge cases—appear throughout computer science.