BST Operations Deep Dive: Insert, Delete & Search

A Binary Search Tree is the most natural way to organize data for fast lookup. Every node enforces a single rule: everything in the left subtree is smaller, everything in the right subtree is larger. This one invariant gives us O(log n) search, insert, and delete — when the tree stays balanced.

The BST property

For every node n in a BST:

• All values in n.left are strictly less than n.val
• All values in n.right are strictly greater than n.val

This must hold recursively for every subtree, not just direct children.

        20
       /  \
      10   30        Valid BST
     / \   / \
    5  15 25  35

A common mistake is only checking the immediate children. The value 25 must be greater than 20 (the root), not just less than 30. The property is global, not local.

The TreeNode class

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

Every BST operation starts from the root and navigates left or right based on comparisons.

Search

Search is the simplest operation. Start at the root, compare, go left or right.

def search(root, target):
    """Return the node with value target, or None."""
    if root is None or root.val == target:
        return root
    if target < root.val:
        return search(root.left, target)
    return search(root.right, target)

Iterative version (saves stack space):

def search_iterative(root, target):
    current = root
    while current:
        if current.val == target:
            return current
        elif target < current.val:
            current = current.left
        else:
            current = current.right
    return None

At each step we eliminate roughly half the tree, giving us O(log n) for a balanced tree.

Search trace example

Search for 15 in:
        20
       /  \
      10   30
     / \
    5  15

Step 1: 15 < 20 → go left
Step 2: 15 > 10 → go right
Step 3: 15 == 15 → found!

Comparisons: 3 (which is the depth of node 15)

Insert

Insertion follows the same path as search. When we reach a None position, that is where the new node belongs.

def insert(root, val):
    """Insert val into BST rooted at root. Return the root."""
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    # If val == root.val, we skip (no duplicates)
    return root

Iterative version:

def insert_iterative(root, val):
    new_node = TreeNode(val)
    if root is None:
        return new_node

    parent = None
    current = root
    while current:
        parent = current
        if val < current.val:
            current = current.left
        elif val > current.val:
            current = current.right
        else:
            return root  # duplicate, skip

    if val < parent.val:
        parent.left = new_node
    else:
        parent.right = new_node
    return root

Insertion order matters

The shape of the BST depends entirely on the insertion order:

# Inserting [4, 2, 6, 1, 3, 5, 7] gives a balanced tree:
#        4
#       / \
#      2   6
#     / \ / \
#    1  3 5  7

# Inserting [1, 2, 3, 4, 5, 6, 7] gives a skewed tree:
# 1
#  \
#   2
#    \
#     3
#      \
#       4  ... (essentially a linked list)

This is why balanced BSTs (AVL, Red-Black) exist — they prevent degradation.

In-order successor and predecessor

Before tackling delete, we need these two concepts.

In-order successor: The node with the smallest value greater than the current node. It is the leftmost node in the right subtree.

In-order predecessor: The node with the largest value smaller than the current node. It is the rightmost node in the left subtree.

def find_min(node):
    """Find the leftmost (minimum) node in the subtree."""
    current = node
    while current.left:
        current = current.left
    return current

def find_max(node):
    """Find the rightmost (maximum) node in the subtree."""
    current = node
    while current.right:
        current = current.right
    return current

For a node with value 20 that has a right subtree, its in-order successor is find_min(node.right).

Delete

Delete is the most complex BST operation because removing a node must preserve the BST property. There are three cases.

Case 1: Delete a leaf node

The simplest case. The node has no children — just remove it.

Delete 5:
    10          10
   / \    →    / \
  5   15         15

Case 2: Delete a node with one child

Replace the node with its only child. The child takes the deleted node’s position.

Delete 10 (has left child 5):
    20          20
   / \    →    / \
  10  30      5   30
 /
5

Case 3: Delete a node with two children

This is the tricky case. We cannot just remove the node because both subtrees need a parent. The strategy:

1. Find the in-order successor (smallest node in right subtree)
2. Copy the successor’s value to the node being deleted
3. Delete the successor (which has at most one child, so it falls into Case 1 or 2)

Delete 20 (has two children):
    20          25
   / \    →    / \
  10  30      10  30
     /
    25

Step 1: In-order successor of 20 = 25 (leftmost in right subtree)
Step 2: Copy 25 to position of 20
Step 3: Delete original 25 (leaf, Case 1)

Complete delete implementation

def delete(root, val):
    """Delete node with value val from BST. Return the root."""
    if root is None:
        return None

    # Navigate to the node
    if val < root.val:
        root.left = delete(root.left, val)
    elif val > root.val:
        root.right = delete(root.right, val)
    else:
        # Found the node to delete

        # Case 1: Leaf node
        if root.left is None and root.right is None:
            return None

        # Case 2: One child
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left

        # Case 3: Two children
        # Find in-order successor (min of right subtree)
        successor = find_min(root.right)
        root.val = successor.val
        # Delete the successor from right subtree
        root.right = delete(root.right, successor.val)

    return root

You could also use the in-order predecessor (max of left subtree) instead of the successor. Both approaches preserve the BST property.

Complete BST class

Here is a full BST class that wraps all operations:

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

    def insert(self, val):
        self.root = self._insert(self.root, val)

    def _insert(self, node, val):
        if node is None:
            return TreeNode(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        return node

    def search(self, val):
        return self._search(self.root, val)

    def _search(self, node, val):
        if node is None or node.val == val:
            return node
        if val < node.val:
            return self._search(node.left, val)
        return self._search(node.right, val)

    def delete(self, val):
        self.root = self._delete(self.root, val)

    def _delete(self, node, val):
        if node is None:
            return None
        if val < node.val:
            node.left = self._delete(node.left, val)
        elif val > node.val:
            node.right = self._delete(node.right, val)
        else:
            if node.left is None:
                return node.right
            if node.right is None:
                return node.left
            successor = self._find_min(node.right)
            node.val = successor.val
            node.right = self._delete(node.right, successor.val)
        return node

    def _find_min(self, node):
        while node.left:
            node = node.left
        return node

    def inorder(self):
        """Return sorted list of values."""
        result = []
        self._inorder(self.root, result)
        return result

    def _inorder(self, node, result):
        if node:
            self._inorder(node.left, result)
            result.append(node.val)
            self._inorder(node.right, result)

Using the BST class

bst = BST()
for val in [20, 10, 30, 5, 15, 25, 35]:
    bst.insert(val)

print(bst.inorder())  # [5, 10, 15, 20, 25, 30, 35]
print(bst.search(15))  # <TreeNode object>
print(bst.search(99))  # None

bst.delete(20)  # Delete root (two children case)
print(bst.inorder())  # [5, 10, 15, 25, 30, 35]

bst.delete(5)   # Delete leaf
print(bst.inorder())  # [10, 15, 25, 30, 35]

Time complexity analysis

Operation	Balanced BST	Skewed BST
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
In-order	O(n)	O(n)
Min/Max	O(log n)	O(n)

Space complexity: O(h) for recursive operations where h is the height. For balanced trees h = log n, for skewed trees h = n.

Why O(log n)?

A balanced BST with n nodes has height approximately log2(n). Each operation visits at most one node per level, so the work is proportional to the height.

# For n = 1,000,000 nodes:
# Balanced: log2(1,000,000) ≈ 20 comparisons
# Skewed: up to 1,000,000 comparisons

The difference is massive. This is why self-balancing trees (AVL, Red-Black) are used in practice.

Validating a BST

A classic interview problem: given a binary tree, check if it is a valid BST.

def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
    """Check if tree is a valid BST using range checking."""
    if root is None:
        return True
    if root.val <= min_val or root.val >= max_val:
        return False
    return (is_valid_bst(root.left, min_val, root.val) and
            is_valid_bst(root.right, root.val, max_val))

The common mistake is only comparing with the parent. You must track the valid range for each node.

Alternative: in-order traversal check

A BST’s in-order traversal produces a sorted sequence. We can verify this:

def is_valid_bst_inorder(root):
    """Validate BST using in-order traversal."""
    prev = [float('-inf')]

    def inorder(node):
        if node is None:
            return True
        if not inorder(node.left):
            return False
        if node.val <= prev[0]:
            return False
        prev[0] = node.val
        return inorder(node.right)

    return inorder(root)

Finding kth smallest element

Another frequent interview problem that leverages in-order traversal:

def kth_smallest(root, k):
    """Find the kth smallest element in BST."""
    count = [0]
    result = [None]

    def inorder(node):
        if node is None or result[0] is not None:
            return
        inorder(node.left)
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        inorder(node.right)

    inorder(root)
    return result[0]

Floor and ceiling

Floor: Largest value in BST that is <= target. Ceiling: Smallest value in BST that is >= target.

def floor(root, target):
    """Find largest value <= target."""
    result = None
    current = root
    while current:
        if current.val == target:
            return current.val
        elif current.val < target:
            result = current.val  # candidate
            current = current.right
        else:
            current = current.left
    return result

def ceiling(root, target):
    """Find smallest value >= target."""
    result = None
    current = root
    while current:
        if current.val == target:
            return current.val
        elif current.val > target:
            result = current.val  # candidate
            current = current.left
        else:
            current = current.right
    return result

Practice problems

1. Validate BST (LeetCode 98) — Use the range-checking approach
2. Insert into BST (LeetCode 701) — Direct application
3. Delete Node in BST (LeetCode 450) — Handle all 3 cases
4. Kth Smallest in BST (LeetCode 230) — In-order traversal
5. Inorder Successor in BST (LeetCode 285) — Use BST property
6. Convert Sorted Array to BST (LeetCode 108) — Divide and conquer
7. Trim a BST (LeetCode 669) — Recursive range trimming
8. Range Sum of BST (LeetCode 938) — Prune branches outside range

Key takeaways

• The BST property is global, not just about direct children
• Delete with two children uses the in-order successor (or predecessor) as a replacement
• All operations are O(h) where h is the height — balanced trees keep h = O(log n)
• In-order traversal of a BST always produces a sorted sequence
• The shape of a BST depends on insertion order, which is why self-balancing variants exist