Binary Search Tree Deletion

For this lesson, keys are distinct and every node’s left subtree contains smaller keys while its right subtree contains larger keys. Search follows that invariant until it finds the target or an empty subtree. A missing target leaves the tree unchanged. Other duplicate-key policies are possible but need their own stated rules.

The deletion function returns the root of the updated subtree. Its caller must store that result in the relevant left/right reference or the overall root. This matters especially when deleting the root or replacing a node with its only child. A return value does not automatically rebind an unrelated variable in the caller.

A leaf has no children, so deleting it returns an empty subtree. A node with one child is replaced by that child, retaining the child’s whole subtree. For a node with two children, use the smallest key in its right subtree as an inorder successor, or an appropriate predecessor from the left under an alternative algorithm.

Copy the successor’s key into the target position, then remove the original successor node from the right subtree. The successor has no left child because it was the smallest there, simplifying its removal. Do not merely delete the entire right subtree or attach children according to their current display position; the ordering invariant, not the drawing layout, controls correctness.

In the example, deleting root key 8 selects successor 9 from the right subtree. The new root key is 9, and the old 9 node is removed. Inorder traversal remains sorted and contains every original key except 8. A sorted output alone does not prove every reference update, so also check node count and the intended remaining keys.

Work is proportional to tree height in this ordinary unbalanced implementation. A balanced shape can give logarithmic height, while a skewed tree can make deletion linear. The recursive implementation also uses call-stack space proportional to height. Test deletion from an empty tree, a missing key, a leaf, a one-child node and a two-child root.

class Node:
    def __init__(self, key, left=None, right=None):
        self.key, self.left, self.right = key, left, right

def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        successor = root.right
        while successor.left is not None:
            successor = successor.left
        root.key = successor.key
        root.right = delete(root.right, successor.key)
    return root

def inorder(root):
    if root is None:
        return []
    return inorder(root.left) + [root.key] + inorder(root.right)

root = Node(8, Node(3, Node(1), Node(6)),
            Node(10, Node(9), Node(14)))
root = delete(root, 8)
print(root.key, inorder(root))

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.