BST Operations

A binary search tree makes search, insert, and delete all run in time proportional to the tree's height — not its size — because at every node the BST invariant (left subtree < node < right subtree) lets you discard one entire subtree with a single comparison, the same halving idea as binary search but on a linked structure instead of an array.

Recognize the pattern

• Data has a total order and you need repeated search / insert / delete / range queries, not just build-once-and-scan.
• You need the sorted order to fall out of a traversal (inorder) rather than re-sorting after every mutation.
• Interview phrasing: "find/insert/delete in a BST", "kth smallest", "validate BST", "closest value", "floor/ceiling".
• Tell that rules it OUT: keys aren't comparable, or you only ever need O(1) min/max (use a heap instead).

Brute force vs optimal

Brute force — keep values in an unsorted array/list. Search is O(n) linear scan, insert is O(1) append but breaks sortedness, delete is O(n) to find plus O(n) to shift. No structure to exploit.

BST — each comparison prunes an entire subtree. Search/insert/delete all become O(h), where h is tree height. The cost you pay: h can degrade from O(log n) to O(n) if insertions arrive in sorted order and you never rebalance (that's what AVL/Red-Black trees fix, at the cost of extra rotation bookkeeping on every insert/delete).

Complexity from first principles

Let h = height of the tree, n = number of nodes. Each recursive step does O(1) work (one comparison) and moves one level down, so the recurrence is T(h) = T(h-1) + O(1), which unrolls to O(h) for search, insert, and the find-node part of delete.

• Balanced tree: each level roughly halves the remaining candidates, so h = O(log n) → operations are O(log n).
• Skewed tree (e.g. inserting 1,2,3,4,5 in order): every node has exactly one child, h = n → operations degrade to O(n).
• Space: recursive implementations use the call stack, O(h) — O(log n) balanced, O(n) skewed. Iterative implementations use O(1) auxiliary space.

Traced example: insert then delete

Start empty, insert in this order: 50, 30, 70, 20, 40, 60.

Now delete(50) — the root, a two-children case. Find the inorder successor = smallest value in right subtree (70's subtree): walk left from 70 → 60 (no left child) → successor = 60. Copy 60 into the root, then delete 60 from the right subtree (60 is a leaf there, so remove it directly). Final tree: root=60, left=30(20,40), right=70(null,null).

Java implementation

class Node {
    int val;
    Node left, right;
    Node(int v) { val = v; }
}

class BST {
    Node insert(Node node, int val) {
        if (node == null) return new Node(val);
        if (val < node.val) node.left = insert(node.left, val);
        else if (val > node.val) node.right = insert(node.right, val);
        return node; // duplicate: no-op
    }

    boolean search(Node node, int key) {
        if (node == null) return false;
        if (key == node.val) return true;
        return key < node.val ? search(node.left, key) : search(node.right, key);
    }

    Node delete(Node node, int key) {
        if (node == null) return null;
        if (key < node.val) { node.left = delete(node.left, key); return node; }
        if (key > node.val) { node.right = delete(node.right, key); return node; }
        // key == node.val: found the node to delete
        if (node.left == null) return node.right;
        if (node.right == null) return node.left;
        Node successor = node.right;
        while (successor.left != null) successor = successor.left;
        node.val = successor.val;
        node.right = delete(node.right, successor.val);
        return node;
    }
}

Pitfalls

• Forgetting to reassign the return value (node.left = insert(node.left, val)) — a common bug that silently drops the insertion because Java passes references by value.
• Using the predecessor and successor inconsistently, or deleting the wrong copy after promoting a successor value (must delete from the right subtree, not just detach a node).
• Assuming O(log n) without checking insertion order — sorted or reverse-sorted input degenerates any unbalanced BST to a linked list.
• Not handling duplicate keys explicitly (decide up front: reject, allow in right subtree, or store a count).

When to use / when not — trade-offs

Use a plain BST when keys are comparable, you need ordered traversal plus reasonably balanced insert patterns, and implementation simplicity matters more than worst-case guarantees.

vs. Balanced BST (AVL/Red-Black): guarantees O(log n) always by rotating on insert/delete, at the cost of extra rotation logic and slightly higher constant factors — pick this when adversarial or sorted input is possible.

vs. Hash Table: hashing gives O(1) average search/insert/delete but no ordering — pick a BST (or balanced variant) when you need range queries, kth-smallest, or sorted iteration; pick a hash table when you only need existence/lookup.

vs. Sorted Array + Binary Search: O(log n) search but O(n) insert/delete due to shifting — pick this only when the data is mostly static (build once, query many times).

Takeaways

• Every BST operation is a walk of length h; the whole game is keeping h close to log n.
• Deletion's two-children case is just "copy the successor's value up, then delete the successor," which is always a leaf-or-one-child case by construction.
• Recursive implementations trade O(h) stack space for clarity; iterative versions get the same time bound in O(1) space.

Recall: Why is deleting a two-children node's inorder successor always a simple leaf-or-one-child deletion, never itself a two-children case?

Synthesized from CLRS (Introduction to Algorithms) Ch. 12, and standard BST treatments (GeeksforGeeks, Princeton COS226).