Binary Search Trees: Invariants, Successor Deletion & Traversal Mechanics

The diagram below displays a canonical Valid Binary Search Tree alongside the Global Subtree Validation Trap:

2. The Three Fundamental Node Deletion Cases

Deleting a node from a BST requires preserving the global ordering invariant. The diagram below illustrates all three structural deletion cases:

The Three Fundamental Node Deletion Cases

Deleting a node from a BST requires preserving the global ordering invariant. There are three distinct structural cases:

1. Case 1 (Leaf Node — 0 Children): The target node has neither left nor right children. The parent pointer referencing this node is simply updated to null.
2. Case 2 (Single Child — 1 Child): The target node has exactly one child (either left or right). The parent pointer is updated to bypass the target node and point directly to its child.
3. Case 3 (Two Children — 2 Children): The target node has both left and right children. Deleting it directly would fracture the tree. Instead:
   • Locate the in-order successor (the minimum key in the right subtree: min(node.right)).
   • Copy the successor's key into the target node.
   • Recursively delete the successor from the right subtree (which is guaranteed to have at most 1 child, reducing to Case 1 or Case 2).

In-Order Traversal & Monotonic Sorting

When performing a Depth-First Search (DFS) in-order traversal (Left → Node → Right) on a valid BST, the retrieved sequence is mathematically guaranteed to be strictly ascending:

In-Order Traversal sequence: [30, 50, 60, 80, 90] (Strictly Sorted)

This property provides an immediate O(N) sorting mechanism and forms the basis for finding the $k^{\text{th}}$ smallest element in O(h + k) time.

Production-Grade Java Implementation

public class BinarySearchTree {
    public static class Node {
        public int key;
        public Node left;
        public Node right;

        public Node(int key) {
            this.key = key;
        }
    }

    private Node root;

    // --- 1. SEARCH: O(h) Iterative ---
    public boolean contains(int key) {
        Node curr = root;
        while (curr != null) {
            if (key == curr.key) return true;
            curr = (key < curr.key) ? curr.left : curr.right;
        }
        return false;
    }

    // --- 2. INSERTION: O(h) Recursive ---
    public void insert(int key) {
        root = insertRecursive(root, key);
    }

    private Node insertRecursive(Node node, int key) {
        if (node == null) return new Node(key);

        if (key < node.key) {
            node.left = insertRecursive(node.left, key);
        } else if (key > node.key) {
            node.right = insertRecursive(node.right, key);
        }
        return node; // Duplicate keys ignored
    }

    // --- 3. DELETION: O(h) Covering All 3 Cases ---
    public void delete(int key) {
        root = deleteRecursive(root, key);
    }

    private Node deleteRecursive(Node node, int key) {
        if (node == null) return null;

        if (key < node.key) {
            node.left = deleteRecursive(node.left, key);
        } else if (key > node.key) {
            node.right = deleteRecursive(node.right, key);
        } else {
            // Case 1 & Case 2: 0 or 1 child
            if (node.left == null) return node.right;
            if (node.right == null) return node.left;

            // Case 3: 2 children -> replace with in-order successor
            Node successor = findMin(node.right);
            node.key = successor.key;
            node.right = deleteRecursive(node.right, successor.key);
        }
        return node;
    }

    private Node findMin(Node node) {
        while (node.left != null) node = node.left;
        return node;
    }

    // --- 4. VALIDATION: Check if binary tree is valid BST ---
    public boolean isValidBST() {
        return validate(root, null, null);
    }

    private boolean validate(Node node, Integer minVal, Integer maxVal) {
        if (node == null) return true;

        if ((minVal != null && node.key <= minVal) || (maxVal != null && node.key >= maxVal)) {
            return false;
        }

        return validate(node.left, minVal, node.key) && validate(node.right, node.key, maxVal);
    }
}

Python Implementation

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

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def search(self, key: int) -> bool:
        curr = self.root
        while curr:
            if key == curr.key:
                return True
            curr = curr.left if key < curr.key else curr.right
        return False

    def insert(self, key: int):
        def _insert(node: TreeNode | None, k: int) -> TreeNode:
            if not node:
                return TreeNode(k)
            if k < node.key:
                node.left = _insert(node.left, k)
            elif k > node.key:
                node.right = _insert(node.right, k)
            return node

        self.root = _insert(self.root, key)

    def delete(self, key: int):
        def _delete(node: TreeNode | None, k: int) -> TreeNode | None:
            if not node:
                return None
            if k < node.key:
                node.left = _delete(node.left, k)
            elif k > node.key:
                node.right = _delete(node.right, k)
            else:
                # 0 or 1 child
                if not node.left:
                    return node.right
                if not node.right:
                    return node.left
                # 2 children: get successor
                successor = node.right
                while successor.left:
                    successor = successor.left
                node.key = successor.key
                node.right = _delete(node.right, successor.key)
            return node

        self.root = _delete(self.root, key)

    def is_valid_bst(self) -> bool:
        def _validate(node: TreeNode | None, min_val: float, max_val: float) -> bool:
            if not node:
                return True
            if not (min_val < node.key < max_val):
                return False
            return _validate(node.left, min_val, node.key) and _validate(node.right, node.key, max_val)

        return _validate(self.root, float("-inf"), float("inf"))

Asymptotic Complexity & The Degeneration Problem