Introduction

Deletion is the trickiest basic operation in a binary search tree because removing a node can break the ordering property if you reconnect the tree incorrectly. In a BST, every node's left subtree contains smaller keys and every right subtree contains larger keys. A correct deletion algorithm preserves that rule in all cases.

The Three Deletion Cases

When you delete a node from a BST, one of three cases applies.

Case one is a leaf node. If the node has no children, you simply remove it.

Case two is a node with one child. In that case, you replace the node with its only child.

Case three is a node with two children. This is the interesting case. You usually replace the node's value with its in-order successor, which is the smallest value in its right subtree, and then delete that successor node from the right subtree.

That works because the successor is the next larger key, so the BST ordering remains valid.

A Recursive Python Implementation

Here is a complete example using the successor approach:

1class Node:
2    def __init__(self, key):
3        self.key = key
4        self.left = None
5        self.right = None
6
7
8def insert(root, key):
9    if root is None:
10        return Node(key)
11    if key < root.key:
12        root.left = insert(root.left, key)
13    elif key > root.key:
14        root.right = insert(root.right, key)
15    return root
16
17
18def find_min(node):
19    while node.left is not None:
20        node = node.left
21    return node
22
23
24def delete(root, key):
25    if root is None:
26        return None
27
28    if key < root.key:
29        root.left = delete(root.left, key)
30    elif key > root.key:
31        root.right = delete(root.right, key)
32    else:
33        if root.left is None:
34            return root.right
35        if root.right is None:
36            return root.left
37
38        successor = find_min(root.right)
39        root.key = successor.key
40        root.right = delete(root.right, successor.key)
41
42    return root
43
44
45def inorder(root):
46    if root is None:
47        return []
48    return inorder(root.left) + [root.key] + inorder(root.right)
49
50
51root = None
52for value in [50, 30, 70, 20, 40, 60, 80]:
53    root = insert(root, value)
54
55root = delete(root, 50)
56print(inorder(root))

Output:

[20, 30, 40, 60, 70, 80]

Deleting 50 works by copying in 60, the smallest key in the original right subtree, then deleting the old 60 node.

Why The Successor Step Works

Suppose a node has two children. If you replaced it with an arbitrary value from one side, you could violate BST ordering immediately. The in-order successor is special because it is greater than every key in the left subtree and no greater than the remaining keys in the right subtree.

You can also use the in-order predecessor, which is the largest key in the left subtree. Both approaches are correct as long as you implement them consistently.

Time Complexity

Deletion takes O(h) time, where h is the tree height, because you follow one path down the tree and possibly another short path to find the successor.

In a balanced BST, h is about log n, which is efficient. In a badly skewed BST, h can become n, which makes deletion linear in the worst case. That is one reason self-balancing trees such as AVL trees and red-black trees are useful in production systems.

Common Pitfalls

The most common bug is forgetting to reassign the returned subtree root. In recursive code, root.left = delete(root.left, key) and root.right = delete(root.right, key) are essential because the child link may change.

Another mistake is handling the two-child case by copying the successor value but forgetting to delete the successor node afterward. That leaves a duplicate key in the tree.

Be careful with duplicate values as well. Some BST implementations allow them and some do not. The insertion and deletion rules must agree on that policy.

Finally, remember that deleting the root node is not a special-case hack if your function returns the new subtree root. The recursive structure handles it naturally.

Summary

• BST deletion has three cases: no child, one child, or two children.
• Leaf nodes are removed directly, and one-child nodes are replaced by their child.
• Two-child deletion usually replaces the node with its in-order successor.
• A correct implementation must reconnect child pointers on the way back up.
• Runtime is O(h), which depends on the height of the tree.