Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Python BST deletion: replace a two-child node with its successor

Last updated: 30 Sept 20264 min read
tutorial
IntermediateBy AITrove Editorial

Binary search tree deletion removes a key while preserving the ordering of keys in every retained subtree.

Download Python source kit

Operation contract

The owned tree stores unique integer receipt numbers. A missing key leaves the tree logically unchanged. A node with zero or one child returns its surviving subtree; a node with two children takes the smallest key from its right subtree and deletes that successor there. The caller must assign the returned root because deleting the root can replace it.

Failure and ownership boundary

This implementation accepts roots created by the bounded builder. It does not validate arbitrary cyclic node graphs. Tree nodes remain mutable and caller-owned; deletion changes them in place. No balancing occurs, so sorted insertion creates a chain. Python iterative tree traversal: shared nodes are not a tree and Python recursion: bound depth instead of raising the limit show why a small fixture cannot establish safe depth for an unbounded service.

Working program

python
from dataclasses import dataclass

@dataclass
class ReceiptNode:
    key: int
    left: "ReceiptNode | None" = None
    right: "ReceiptNode | None" = None

def receipt_tree(keys):
    if len(keys) > 64 or any(type(key) is not int for key in keys) or len(set(keys)) != len(keys):
        raise ValueError("bounded unique integer keys required")
    def insert(root, key):
        if root is None:
            return ReceiptNode(key)
        if key < root.key:
            root.left = insert(root.left, key)
        else:
            root.right = insert(root.right, key)
        return root
    root = None
    for key in keys:
        root = insert(root, key)
    return root

def delete_receipt(root, key):
    if type(key) is not int:
        raise ValueError("integer key required")
    if root is None:
        return None
    if key < root.key:
        root.left = delete_receipt(root.left, key)
    elif key > root.key:
        root.right = delete_receipt(root.right, key)
    elif root.left is None:
        return root.right
    elif root.right is None:
        return root.left
    else:
        successor = root.right
        while successor.left is not None:
            successor = successor.left
        root.key = successor.key
        root.right = delete_receipt(root.right, successor.key)
    return root

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

root = receipt_tree([41, 20, 60, 50, 70])
root = delete_receipt(root, 41)
print(ordered_receipts(root))
root = delete_receipt(root, 999)
print(ordered_receipts(root))

Output

Output
[20, 50, 60, 70]
[20, 50, 60, 70]

Costs and limits

Deletion costs O(h) traversal work and O(h) call-stack space for height h; h can equal n. The display helper concatenates lists and can cost O(n squared) on a chain. It is bounded here and is not the deletion algorithm’s storage cost.

Common Mistakes

  • Always retain the returned root after deletion.
  • Successor replacement must also remove the successor from its old subtree.

Connected lessons

Python iterative tree traversal: shared nodes are not a tree, Python recursion: bound depth instead of raising the limit, Python linked-list reversal: validate cycles before changing links.

Follow the related contract

Python AVL insertion: rotate while preserving ordered keys and heights.

Check the next state boundary

Python AVL deletion: rebalance after removing a key and replacing its successor.

python
bst-deletion
Storage details