deletion in a binary search tree

binary search tree

deletion algorithm

data structures

tree manipulation

coding techniques

deletion in a binary search tree

Master System Design with Codemia

Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.

Start Practicing Learn More

Introduction

Deleting a node from a Binary Search Tree (BST) is more complex than insertion or search because removing a node must preserve the BST property: every node's left subtree contains only smaller keys, and every node's right subtree contains only larger keys. There are three cases to handle depending on how many children the target node has.

BST Property Recap

For every node in a BST:

All keys in the left subtree are less than the node's key
All keys in the right subtree are greater than the node's key

This property must be maintained after every deletion.

The Three Deletion Cases

Case 1: Node Has No Children (Leaf Node)

Simply remove the node:

1Before:          After deleting 4:
2      5                5
3     / \              / \
4    3   7            3   7
5   / \              /
6  1   4            1

Case 2: Node Has One Child

Replace the node with its only child:

1Before:          After deleting 3:
2      5                5
3     / \              / \
4    3   7            1   7
5   /
6  1

Case 3: Node Has Two Children

This is the complex case. Replace the node with either:

Its in-order successor (smallest node in the right subtree), or
Its in-order predecessor (largest node in the left subtree)

Then delete that successor/predecessor from its original position.

1Before:          After deleting 5 (using in-order successor 6):
2      5                6
3     / \              / \
4    3   8            3   8
5   / \  /           / \  /
6  1  4 6           1  4 7
7      \
8       7

Implementation in Python

python

1class TreeNode:
2    def __init__(self, key):
3        self.key = key
4        self.left = None
5        self.right = None
6
7def delete_node(root, key):
8    if root is None:
9        return None
10
11    # Search for the node
12    if key < root.key:
13        root.left = delete_node(root.left, key)
14    elif key > root.key:
15        root.right = delete_node(root.right, key)
16    else:
17        # Found the node to delete
18
19        # Case 1 & 2: No child or one child
20        if root.left is None:
21            return root.right
22        if root.right is None:
23            return root.left
24
25        # Case 3: Two children
26        # Find in-order successor (smallest in right subtree)
27        successor = find_min(root.right)
28        root.key = successor.key
29        root.right = delete_node(root.right, successor.key)
30
31    return root
32
33def find_min(node):
34    while node.left is not None:
35        node = node.left
36    return node

Implementation in Java

java

1class TreeNode {
2    int key;
3    TreeNode left, right;
4
5    TreeNode(int key) {
6        this.key = key;
7    }
8}
9
10class BST {
11    TreeNode delete(TreeNode root, int key) {
12        if (root == null) return null;
13
14        if (key < root.key) {
15            root.left = delete(root.left, key);
16        } else if (key > root.key) {
17            root.right = delete(root.right, key);
18        } else {
19            // Case 1 & 2
20            if (root.left == null) return root.right;
21            if (root.right == null) return root.left;
22
23            // Case 3
24            TreeNode successor = findMin(root.right);
25            root.key = successor.key;
26            root.right = delete(root.right, successor.key);
27        }
28        return root;
29    }
30
31    TreeNode findMin(TreeNode node) {
32        while (node.left != null)
33            node = node.left;
34        return node;
35    }
36}

Implementation in C++

cpp

1struct TreeNode {
2    int key;
3    TreeNode* left;
4    TreeNode* right;
5    TreeNode(int k) : key(k), left(nullptr), right(nullptr) {}
6};
7
8TreeNode* findMin(TreeNode* node) {
9    while (node->left)
10        node = node->left;
11    return node;
12}
13
14TreeNode* deleteNode(TreeNode* root, int key) {
15    if (!root) return nullptr;
16
17    if (key < root->key) {
18        root->left = deleteNode(root->left, key);
19    } else if (key > root->key) {
20        root->right = deleteNode(root->right, key);
21    } else {
22        if (!root->left) {
23            TreeNode* right = root->right;
24            delete root;
25            return right;
26        }
27        if (!root->right) {
28            TreeNode* left = root->left;
29            delete root;
30            return left;
31        }
32        TreeNode* successor = findMin(root->right);
33        root->key = successor->key;
34        root->right = deleteNode(root->right, successor->key);
35    }
36    return root;
37}

Iterative Deletion

An iterative approach avoids recursion overhead:

python

1def delete_iterative(root, key):
2    parent = None
3    current = root
4
5    # Find the node and its parent
6    while current and current.key != key:
7        parent = current
8        if key < current.key:
9            current = current.left
10        else:
11            current = current.right
12
13    if current is None:
14        return root  # Key not found
15
16    # Case 3: Two children
17    if current.left and current.right:
18        successor_parent = current
19        successor = current.right
20        while successor.left:
21            successor_parent = successor
22            successor = successor.left
23        current.key = successor.key
24        current = successor
25        parent = successor_parent
26
27    # Case 1 & 2: Zero or one child
28    child = current.left if current.left else current.right
29
30    if parent is None:
31        return child  # Deleting root
32    elif parent.left == current:
33        parent.left = child
34    else:
35        parent.right = child
36
37    return root

Time and Space Complexity

Operation	Average	Worst (Skewed Tree)
Search	O(log n)	O(n)
Delete	O(log n)	O(n)
Find successor	O(log n)	O(n)
Space (recursive)	O(log n) stack	O(n) stack
Space (iterative)	O(1)	O(1)

The worst case occurs when the tree is completely unbalanced (essentially a linked list). Use self-balancing BSTs (AVL, Red-Black) for guaranteed O(log n) operations.

Common Pitfalls

Not handling root deletion: If the deleted node is the root and has zero or one child, the root reference must be updated. Always return the (possibly new) root from the delete function.
In-order predecessor vs successor: Both work correctly. Using the successor (min of right subtree) is more common, but using the predecessor (max of left subtree) is equally valid. Alternating between them can help keep the tree balanced.
Forgetting to reconnect subtrees: When replacing a node with its successor, you must delete the successor from its original position. Otherwise, the successor appears twice in the tree.
Memory leaks in C/C++: When deleting a node, free its memory. The recursive approach above handles this in the base cases for zero/one child, but the two-child case only copies the key — the actual successor node is freed in the recursive call.
Duplicate keys: Standard BST deletion assumes unique keys. If duplicates exist, decide whether to delete all occurrences or just one, and handle accordingly.

Summary

BST deletion has three cases: leaf node (remove), one child (replace with child), two children (replace with in-order successor then delete successor)
The in-order successor is the smallest node in the right subtree
Recursive implementation is cleaner; iterative avoids stack overflow for deep trees
Average time complexity is O(log n); worst case is O(n) for skewed trees
Use self-balancing BSTs (AVL, Red-Black) for guaranteed O(log n) deletion