bhylu.com

Advertisements

DSA BST Deletion

Deleting a search-tree key has different cases for no child, one child and two children. The returned root can change, just as the head can change in a linked list.

How it works

For two children, this key-only implementation copies the inorder successor key from the right subtree, then removes that successor node. It does not preserve a separate node identity or payload association, so an application storing records must move or associate payloads consistently. Missing keys leave the tree unchanged. The recursive deletion expects a tree shallow enough for the reviewed interpreter’s normal recursion limit.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as bst-delete.py and run python bst-delete.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

bst-delete.py
Try in playground

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

def insert(root, key):
    if root is None:
        return TreeNode(key)
    current = root
    while True:
        if key == current.key:
            return root
        side = "left" if key < current.key else "right"
        child = getattr(current, side)
        if child is None:
            setattr(current, side, TreeNode(key))
            return root
        current = child

def contains(root, key):
    while root is not None:
        if key == root.key:
            return True
        root = root.left if key < root.key else root.right
    return False

def ordered(root):
    result, pending = [], []
    while root is not None or pending:
        while root is not None:
            pending.append(root)
            root = root.left
        root = pending.pop()
        result.append(root.key)
        root = root.right
    return result

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

root = None
for key in [8, 3, 12, 10, 14]:
    root = insert(root, key)
root = delete(root, 8)
root = delete(root, 99)
print(ordered(root))

Expected result

[3, 10, 12, 14]

Removing the original root retains all other keys in order, and the absent-key request has no additional effect. Tests also cover empty trees, leaves and single-child roots to make the returned-root contract meaningful.

Time, space and assumptions

Deletion takes O(h) search/relink work and O(h) recursive frames for height h. Worst-case h can be n in this unbalanced tree; the separate output traversal adds its own O(n) work.

Consult the Python 3.12 standard-library reference for container and language contracts; an example result is not a proof of every possible input or real-world performance.

Advertisements