AtticBinary Search Trees
Inorder sorted property, logarithmic search, insertion, 3-case deletion, and BST validation
A Binary Search Tree (BST) is a node-based binary tree data structure with the following ordering invariant:
- The left subtree of a node contains only keys strictly less than the node's key.
- The right subtree of a node contains only keys strictly greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
The Golden Property of BST: An inorder traversal (left -> root -> right) of a Binary Search Tree always visits values in strictly ascending sorted order.
1. Search Operation
Because subtrees are partitioned by value, binary search eliminates half of the remaining nodes at each step:
public TreeNode searchBST(TreeNode root, int val) {
TreeNode curr = root;
while (curr != null && curr.val != val) {
if (val < curr.val) {
curr = curr.left;
} else {
curr = curr.right;
}
}
return curr; // null if not found
}2. Insert Operation
Insertion always lands at a null leaf position that preserves the BST invariant:
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else if (val > root.val) {
root.right = insertIntoBST(root.right, val);
}
return root;
}3. Delete Operation (The 3 Classic Cases)
Deleting a node from a BST is one of the most celebrated algorithmic problems because removing an internal node cannot violate subtree ordering.
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
// Found node to delete
// Case 1 & 2: 0 or 1 child
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// Case 3: Node with 2 children
// Find Inorder Successor (minimum node in right subtree)
TreeNode successor = getMin(root.right);
// Copy successor's value to current node
root.val = successor.val;
// Recursively delete the successor from the right subtree
root.right = deleteNode(root.right, successor.val);
}
return root;
}
private TreeNode getMin(TreeNode node) {
while (node.left != null) {
node = node.left;
}
return node;
}4. Validating a Binary Search Tree
The Local Invariant Trap: It is not enough to check node.left.val < node.val && node.right.val > node.val locally! Every node in the left subtree must be less than all ancestors above it.
5
/ \
1 4
/ \
3 6In the tree above, 4.left = 3 and 4.right = 6 are locally valid around node 4, but 3 is in the right subtree of 5 (violating 3 > 5). The entire tree is invalid.
Correct Boundary Propagation Validation:
Pass valid min and max boundaries down the recursion tree:
public boolean isValidBST(TreeNode root) {
// Use Long.MIN_VALUE and Long.MAX_VALUE to prevent Integer overflow
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean validate(TreeNode node, long min, long max) {
if (node == null) return true;
if (node.val <= min || node.val >= max) {
return false;
}
// Left subtree must be < node.val; Right subtree must be > node.val
return validate(node.left, min, node.val) &&
validate(node.right, node.val, max);
}5. Lowest Common Ancestor (LCA) in BST
Unlike a general binary tree which requires bottom-up postorder traversal, LCA in a BST takes advantage of the sorted property in O(h) time and O(1) space:
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode curr = root;
while (curr != null) {
// Both nodes lie in the left subtree
if (p.val < curr.val && q.val < curr.val) {
curr = curr.left;
}
// Both nodes lie in the right subtree
else if (p.val > curr.val && q.val > curr.val) {
curr = curr.right;
}
// Split point found: curr is the LCA!
else {
return curr;
}
}
return null;
}Performance Summary
| Operation | Average Case (Balanced BST) | Worst Case (Degenerate / Skewed BST) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Inorder Traversal | O(n) | O(n) |
| Space (Recursion) | O(log n) | O(n) |
Why Self-Balancing Is Necessary: When items are inserted in sorted order (1, 2, 3, 4, 5), an
unaugmented BST degenerates into a singly-linked list with height n, reducing logarithmic
operations to linear scans. To prevent this, production systems use self-balancing trees like
AVL Trees and Red-Black Trees.