How to Delete a Node in a BST While Maintaining Binary Search Tree Integrity

Deleting a node from a binary search tree requires handling three distinct cases—leaf nodes, single-child nodes, and two-child nodes—by either unlinking the node, promoting its child, or substituting it with its in-order successor to preserve the BST ordering invariant.

The python/cpython repository demonstrates fundamental ordered data structures through modules like bisect, yet implementing a custom binary search tree requires careful pointer manipulation during deletion. When you delete a node in a BST, you must restructure the tree to ensure the invariant remains intact: all left descendants contain keys smaller than the parent, and all right descendants contain keys larger than the parent.

The Three Cases of BST Node Deletion

Binary search tree deletion algorithms distinguish between three structural scenarios. Each case requires a specific pointer manipulation strategy to maintain tree integrity.

Case 1 – Deleting a Leaf Node

When the target node has no children (both left and right pointers are None), deletion is straightforward. Simply unlink the node from its parent by setting the parent's corresponding child pointer to None. This operation preserves the BST property because no subtree relationships require reorganization.

Case 2 – Deleting a Node with One Child

If the node has exactly one non-null child, splice the node out of the tree by replacing it with its sole child. The child inherits the deleted node's parent link, maintaining the ordering of all descendants while removing the target key. This requires updating the parent's pointer to reference the child directly.

Case 3 – Deleting a Node with Two Children

This scenario requires finding a replacement node that maintains the ordering invariant. Locate either the in-order predecessor (the maximum node in the left subtree) or the in-order successor (the minimum node in the right subtree). Copy that replacement node's key and value into the node to delete, then recursively delete the replacement node from its original position.

The replacement node is guaranteed to have at most one child (the successor has no left child; the predecessor has no right child), so this recursive step collapses into Case 1 or Case 2. On a balanced BST, this guarantees O(log n) time complexity.

Python Implementation Reference

While CPython does not ship a generic BST implementation in its standard library, the Lib/bisect.py module provides canonical binary search logic for sorted sequences. The following self-contained implementation demonstrates the three-case deletion strategy suitable for production use:

class BSTNode:
    __slots__ = ("key", "value", "left", "right")
    def __init__(self, key, value=None):
        self.key = key
        self.value = value
        self.left = self.right = None


class BinarySearchTree:
    """Simple BST supporting insert, search, and delete in O(log n) on a
    balanced tree. The delete method follows the three-case algorithm."""
    def __init__(self):
        self.root = None

    def insert(self, key, value=None):
        node = BSTNode(key, value)
        if not self.root:
            self.root = node
            return
        cur = self.root
        while True:
            if key < cur.key:
                if cur.left:
                    cur = cur.left
                else:
                    cur.left = node
                    return
            elif key > cur.key:
                if cur.right:
                    cur = cur.right
                else:
                    cur.right = node
                    return
            else:
                cur.value = value
                return

    def _search(self, key):
        cur = self.root
        while cur and cur.key != key:
            cur = cur.left if key < cur.key else cur.right
        return cur

    def delete(self, key):
        self.root = self._delete_rec(self.root, key)

    def _delete_rec(self, node, key):
        if not node:
            return None

        if key < node.key:
            node.left = self._delete_rec(node.left, key)
            return node
        if key > node.key:
            node.right = self._delete_rec(node.right, key)
            return node

        # Case 1: leaf

        if not node.left and not node.right:
            return None

        # Case 2: one child

        if not node.left:
            return node.right
        if not node.right:
            return node.left

        # Case 3: two children → use inorder successor

        succ = self._min_node(node.right)
        node.key, node.value = succ.key, succ.value
        node.right = self._delete_rec(node.right, succ.key)
        return node

    def _min_node(self, node):
        """Return the left-most (minimum) node in the subtree."""
        while node.left:
            node = node.left
        return node

The _delete_rec method returns the new subtree root after deletion, allowing parent pointers to update automatically through assignment. The implementation selects the in-order successor via _min_node(node.right), ensuring the replacement has at most one child and guaranteeing logarithmic recursion depth on balanced trees.

Time Complexity Analysis

On a balanced binary search tree, deletion runs in O(log n) time because the algorithm traverses from root to leaf exactly once, and the recursive successor deletion also follows a single path down the tree. In the worst case of a degenerate (unbalanced) tree resembling a linked list, complexity degrades to O(n) as the traversal may visit every node.

Key CPython Source References

Several files in the CPython repository provide relevant implementation patterns for ordered data structures:

• Lib/bisect.py – Contains Python's canonical binary-search implementation for sorted lists, demonstrating the comparison logic useful for BST navigation.
• Objects/abstract.c – Houses generic object comparison utilities that custom tree implementations rely on for key ordering.
• Modules/_abc.c – Provides the abstract-base-class infrastructure helpful when exposing a BST via collections.abc.MutableMapping.
• Lib/heapq.py – Implements a binary heap priority queue, offering an alternative tree-based structure for ordered retrieval without strict BST ordering requirements.
• Doc/tutorial/datastructures.rst – Discusses built-in containers and provides context for when custom data structures like BSTs become necessary.

Summary

• Leaf deletion requires only unlinking the node from its parent pointer.
• Single-child deletion replaces the node with its sole descendant, maintaining subtree relationships.
• Two-child deletion copies the in-order successor (or predecessor) into the target node, then recursively deletes the successor, which is guaranteed to have at most one child.
• The algorithm achieves O(log n) performance on balanced trees but degrades to O(n) on degenerate structures.
• CPython's Lib/bisect.py offers binary search primitives useful for ordered collections, though it operates on lists rather than trees.

Frequently Asked Questions

What is the time complexity to delete a node in a BST?

On a balanced BST, deletion operates in O(log n) time because the algorithm traverses the height of the tree exactly once. For unbalanced trees that resemble linked lists, the worst-case complexity becomes O(n) as the traversal may visit every node.

Should I use the in-order predecessor or successor when deleting a node with two children?

Either choice maintains BST integrity. The in-order successor (minimum of the right subtree) is commonly used because it guarantees the replacement has at most one child, ensuring the recursive deletion terminates quickly. Some implementations alternate between predecessor and successor to maintain better tree balance over many deletions.

Does CPython include a built-in BST implementation?

No, the CPython standard library does not include a generic BST class. However, the bisect module in Lib/bisect.py provides binary search capabilities for sorted lists, and you can combine this with list insertion to create an ordered collection. For tree-based ordered maps, you must implement your own BST or use third-party libraries.

How does BST deletion compare to using bisect on a sorted list?

Deleting from a BST requires O(log n) pointer updates on a balanced tree, while deleting from a Python list (even with bisect to find the position) requires O(n) time to shift elements and maintain contiguous memory. BSTs offer superior asymptotic performance for dynamic ordered collections with frequent insertions and deletions.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}