Delete a Key from a BST

28 min · Intermediate

Insert only adds a leaf, but delete has to remove a node from the middle without breaking the BST rule. Which node takes its place depends on how many children it has.

Three cases

Inorder successor of a node is the next larger key in the tree. When the node has a right child, it is the leftmost node of the right subtree.

First search for the key. When the node is found there are three cases. A leaf is simply removed. A node with one child is replaced by that child. A node with two children needs a stand-in key.

The smallest node of a subtree

The successor is the smallest key in the right subtree, so walk left until there is no left child. The same walk finds the minimum of any subtree.

Python

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

This loop assumes the node is not None. It costs O(h), the length of the left chain.

Delete returns the new subtree

Delete is recursive and returns the root of the subtree after the removal. The parent stores the result, so removing a leaf or a one-child node is just returning something else.

Python

1def delete(node, key):2    if node is None:3        return None4    if key < node.key:5        node.left = delete(node.left, key)6    elif key > node.key:7        node.right = delete(node.right, key)8    else:9        return remove_node(node)10    return node

Going down works like search. node.left = delete(node.left, key) links the parent to whatever the child returns. A missing key reaches None and nothing changes.

The found-node cases

If one child is missing, return the other one, which also covers a leaf. With two children, copy the successor's key into the node, then delete that key from the right subtree.

Python

1def remove_node(node):2    if node.left is None:3        return node.right4    if node.right is None:5        return node.left6    successor = smallest(node.right)7    node.key = successor.key8    node.right = delete(node.right, successor.key)9    return node

Example 1 · Delete a leaf and a one-child node

Python

1class Node:2    def __init__(self, key):3        self.key = key4        self.left = None5        self.right = None6
7def insert(node, key):8    if node is None:9        return Node(key)10    if key < node.key:11        node.left = insert(node.left, key)12    elif key > node.key:13        node.right = insert(node.right, key)14    return node15
16def smallest(node):17    while node.left is not None:18        node = node.left19    return node20
21def delete(node, key):22    if node is None:23        return None24    if key < node.key:25        node.left = delete(node.left, key)26    elif key > node.key:27        node.right = delete(node.right, key)28    else:29        if node.left is None:30            return node.right31        if node.right is None:32            return node.left33        successor = smallest(node.right)34        node.key = successor.key35        node.right = delete(node.right, successor.key)36    return node37
38def preorder(node):39    if node is not None:40        yield node.key41        yield from preorder(node.left)42        yield from preorder(node.right)43
44root = None45for key in [8, 3, 10, 1, 6, 14, 13]:46    root = insert(root, key)47root = delete(root, 1)48print(list(preorder(root)))49root = delete(root, 14)50print(list(preorder(root)))

Output

[8, 3, 6, 10, 14, 13]
[8, 3, 6, 10, 13]

What this code does

Preorder lists a node first, then its left side, then its right side, so it shows the shape.
1 is a leaf and just disappears. 14 has one child, 13, which takes its place under 10.

Example 2 · Delete a node with two children

Python

1class Node:2    def __init__(self, key):3        self.key = key4        self.left = None5        self.right = None6
7def insert(node, key):8    if node is None:9        return Node(key)10    if key < node.key:11        node.left = insert(node.left, key)12    elif key > node.key:13        node.right = insert(node.right, key)14    return node15
16def smallest(node):17    while node.left is not None:18        node = node.left19    return node20
21def delete(node, key):22    if node is None:23        return None24    if key < node.key:25        node.left = delete(node.left, key)26    elif key > node.key:27        node.right = delete(node.right, key)28    else:29        if node.left is None:30            return node.right31        if node.right is None:32            return node.left33        successor = smallest(node.right)34        node.key = successor.key35        node.right = delete(node.right, successor.key)36    return node37
38def preorder(node):39    if node is not None:40        yield node.key41        yield from preorder(node.left)42        yield from preorder(node.right)43
44root = None45for key in [8, 3, 10, 1, 6, 14, 4, 7, 13]:46    root = insert(root, key)47root = delete(root, 3)48print(list(preorder(root)))

Output

[8, 4, 1, 6, 7, 10, 14, 13]

What this code does

3 has children 1 and 6. The smallest key in 6's subtree is 4, so 4 takes 3's place.
Then the old 4 is deleted from the right subtree, a leaf case. The tree matches the picture.

Example 3 · Delete the root

Python

1class Node:2    def __init__(self, key):3        self.key = key4        self.left = None5        self.right = None6
7def insert(node, key):8    if node is None:9        return Node(key)10    if key < node.key:11        node.left = insert(node.left, key)12    elif key > node.key:13        node.right = insert(node.right, key)14    return node15
16def smallest(node):17    while node.left is not None:18        node = node.left19    return node20
21def delete(node, key):22    if node is None:23        return None24    if key < node.key:25        node.left = delete(node.left, key)26    elif key > node.key:27        node.right = delete(node.right, key)28    else:29        if node.left is None:30            return node.right31        if node.right is None:32            return node.left33        successor = smallest(node.right)34        node.key = successor.key35        node.right = delete(node.right, successor.key)36    return node37
38def preorder(node):39    if node is not None:40        yield node.key41        yield from preorder(node.left)42        yield from preorder(node.right)43
44root = None45for key in [8, 3, 10, 1, 6, 14, 4, 7, 13]:46    root = insert(root, key)47root = delete(root, 8)48print(root.key)49print(list(preorder(root)))

Output

10
[10, 3, 1, 6, 4, 7, 14, 13]

What this code does

The successor of 8 is 10, the smallest key of its right subtree. 10 has no left child, so its right child 14 moves up.
Delete may change the root, so always write root = delete(root, key).

Example 4 · A key that is not there

Python

1class Node:2    def __init__(self, key):3        self.key = key4        self.left = None5        self.right = None6
7def insert(node, key):8    if node is None:9        return Node(key)10    if key < node.key:11        node.left = insert(node.left, key)12    elif key > node.key:13        node.right = insert(node.right, key)14    return node15
16def smallest(node):17    while node.left is not None:18        node = node.left19    return node20
21def delete(node, key):22    if node is None:23        return None24    if key < node.key:25        node.left = delete(node.left, key)26    elif key > node.key:27        node.right = delete(node.right, key)28    else:29        if node.left is None:30            return node.right31        if node.right is None:32            return node.left33        successor = smallest(node.right)34        node.key = successor.key35        node.right = delete(node.right, successor.key)36    return node37
38def preorder(node):39    if node is not None:40        yield node.key41        yield from preorder(node.left)42        yield from preorder(node.right)43
44root = None45for key in [8, 3, 10, 1, 6, 14, 4, 7, 13]:46    root = insert(root, key)47before = list(preorder(root))48root = delete(root, 99)49print(before == list(preorder(root)))50single = delete(Node(5), 5)51print(single)

Output

True
None

What this code does

The search reaches None and nothing changes.
Deleting the only node returns None, which is an empty tree.

remove_node is the found case of delete. The successor has no left child, so its own delete is the easy case. The rule still holds: the copied key is larger than everything on the left and smaller than the rest of the right. The whole delete costs O(h).

Next step

Check your understanding

11 quick questions

Three cases

Inorder successor of a node is the next larger key in the tree. When the node has a right child, it is the leftmost node of the right subtree.

First search for the key. When the node is found there are three cases. A leaf is simply removed. A node with one child is replaced by that child. A node with two children needs a stand-in key.

1def delete(node, key):2 if node is None:3 return None4 if key < node.key:5 node.left = delete(node.left, key)6 elif key > node.key:7 node.right = delete(node.right, key)8 else:9 return remove_node(node)10 return node

1def remove_node(node):2 if node.left is None:3 return node.right4 if node.right is None:5 return node.left6 successor = smallest(node.right)7 node.key = successor.key8 node.right = delete(node.right, successor.key)9 return node

1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6 7def insert(node, key):8 if node is None:9 return Node(key)10 if key < node.key:11 node.left = insert(node.left, key)12 elif key > node.key:13 node.right = insert(node.right, key)14 return node15 16def smallest(node):17 while node.left is not None:18 node = node.left19 return node20 21def delete(node, key):22 if node is None:23 return None24 if key < node.key:25 node.left = delete(node.left, key)26 elif key > node.key:27 node.right = delete(node.right, key)28 else:29 if node.left is None:30 return node.right31 if node.right is None:32 return node.left33 successor = smallest(node.right)34 node.key = successor.key35 node.right = delete(node.right, successor.key)36 return node37 38def preorder(node):39 if node is not None:40 yield node.key41 yield from preorder(node.left)42 yield from preorder(node.right)43 44root = None45for key in [8, 3, 10, 1, 6, 14, 13]:46 root = insert(root, key)47root = delete(root, 1)48print(list(preorder(root)))49root = delete(root, 14)50print(list(preorder(root)))

1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6 7def insert(node, key):8 if node is None:9 return Node(key)10 if key < node.key:11 node.left = insert(node.left, key)12 elif key > node.key:13 node.right = insert(node.right, key)14 return node15 16def smallest(node):17 while node.left is not None:18 node = node.left19 return node20 21def delete(node, key):22 if node is None:23 return None24 if key < node.key:25 node.left = delete(node.left, key)26 elif key > node.key:27 node.right = delete(node.right, key)28 else:29 if node.left is None:30 return node.right31 if node.right is None:32 return node.left33 successor = smallest(node.right)34 node.key = successor.key35 node.right = delete(node.right, successor.key)36 return node37 38def preorder(node):39 if node is not None:40 yield node.key41 yield from preorder(node.left)42 yield from preorder(node.right)43 44root = None45for key in [8, 3, 10, 1, 6, 14, 4, 7, 13]:46 root = insert(root, key)47root = delete(root, 3)48print(list(preorder(root)))

1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6 7def insert(node, key):8 if node is None:9 return Node(key)10 if key < node.key:11 node.left = insert(node.left, key)12 elif key > node.key:13 node.right = insert(node.right, key)14 return node15 16def smallest(node):17 while node.left is not None:18 node = node.left19 return node20 21def delete(node, key):22 if node is None:23 return None24 if key < node.key:25 node.left = delete(node.left, key)26 elif key > node.key:27 node.right = delete(node.right, key)28 else:29 if node.left is None:30 return node.right31 if node.right is None:32 return node.left33 successor = smallest(node.right)34 node.key = successor.key35 node.right = delete(node.right, successor.key)36 return node37 38def preorder(node):39 if node is not None:40 yield node.key41 yield from preorder(node.left)42 yield from preorder(node.right)43 44root = None45for key in [8, 3, 10, 1, 6, 14, 4, 7, 13]:46 root = insert(root, key)47root = delete(root, 8)48print(root.key)49print(list(preorder(root)))

1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6 7def insert(node, key):8 if node is None:9 return Node(key)10 if key < node.key:11 node.left = insert(node.left, key)12 elif key > node.key:13 node.right = insert(node.right, key)14 return node15 16def smallest(node):17 while node.left is not None:18 node = node.left19 return node20 21def delete(node, key):22 if node is None:23 return None24 if key < node.key:25 node.left = delete(node.left, key)26 elif key > node.key:27 node.right = delete(node.right, key)28 else:29 if node.left is None:30 return node.right31 if node.right is None:32 return node.left33 successor = smallest(node.right)34 node.key = successor.key35 node.right = delete(node.right, successor.key)36 return node37 38def preorder(node):39 if node is not None:40 yield node.key41 yield from preorder(node.left)42 yield from preorder(node.right)43 44root = None45for key in [8, 3, 10, 1, 6, 14, 4, 7, 13]:46 root = insert(root, key)47before = list(preorder(root))48root = delete(root, 99)49print(before == list(preorder(root)))50single = delete(Node(5), 5)51print(single)