Core Data Structures

Binary Search Trees

A binary search tree (BST) keeps every left-subtree key smaller and every right-subtree key larger than its node — giving O(h) search, insert, and delete, where h is the tree's height. The catch: nothing keeps h small on its own.

BST invariant: for every node, left subtree keys < node key < right subtree keys, recursively
Inorder traversal of a BST visits keys in sorted order — this falls directly out of the invariant
Search, insert, and simple delete are all O(h) — O(log n) if balanced, O(n) in the worst case
Inserting already-sorted data into a plain BST degenerates it into a linked list — h = n
Deleting a node with two children requires finding its inorder successor (or predecessor) to replace it
Self-balancing variants (AVL, red-black — Balanced Trees) guarantee O(log n) height regardless of insertion order

Search and insert, both O(h)

static TreeNode search(TreeNode n, int key) {
    if (n == null || n.val() == key) return n;
    return key < n.val() ? search(n.left(), key) : search(n.right(), key);
}

static TreeNode insert(TreeNode n, int key) {
    if (n == null) return new TreeNode(key, null, null);
    if (key < n.val())      return new TreeNode(n.val(), insert(n.left(), key), n.right());
    else if (key > n.val()) return new TreeNode(n.val(), n.left(), insert(n.right(), key));
    return n;                 // key already present, no duplicate
}

BST operation cost, balanced vs. degenerate
Operation	Balanced (h = O(log n))	Degenerate (h = O(n))
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Find min/max	O(log n) — leftmost/rightmost path	O(n)
Inorder traversal (all keys, sorted)	O(n)	O(n)

Deletion is the operation that trips people up. Deleting a leaf or a node with one child is easy — splice it out. Deleting a node with two children requires preserving the BST invariant: replace the node's key with its inorder successor (the smallest key in the right subtree, found by walking left as far as possible) or inorder predecessor, then delete that successor from its original position — which is now guaranteed to have at most one child.