Pattern Guide
BST Operations & Properties
"BST insert, delete, validate, floor/ceiling, kth element, convert to/from sorted."
Binary Search Tree operations leverage the BST property: left < root < right. Key operations: search/insert O(h), delete O(h) (3 cases: leaf, one child, two children → replace with inorder successor), validate (pass min/max bounds down), floor/ceiling, kth smallest (inorder + counter), and convert sorted array to balanced BST. All degrade to O(n) for unbalanced trees.
Problems you can solve with this pattern
5 problems · click any to start solving
// Delete node from BST
function deleteNode(root, key) {
if (!root) return null;
if (key < root.val) { root.left = deleteNode(root.left, key); }
else if (key > root.val) { root.right = deleteNode(root.right, key); }
else {
if (!root.left) return root.right; // 0 or 1 child
if (!root.right) return root.left;
// Two children: find inorder successor (min of right subtree)
let succ = root.right;
while (succ.left) succ = succ.left;
root.val = succ.val; // copy successor's value
root.right = deleteNode(root.right, succ.val); // delete successor
}
return root;
}
// Validate BST with bounds
function isValidBST(node, min = -Infinity, max = Infinity) {
if (!node) return true;
if (node.val <= min || node.val >= max) return false;
return isValidBST(node.left, min, node.val) &&
isValidBST(node.right, node.val, max);
}BST delete: (1) leaf → remove. (2) one child → replace with child. (3) two children → find inorder successor (leftmost of right subtree), copy its value, delete the successor. BST validation: pass (min, max) bounds to each node — node value must be strictly within bounds. Kth smallest: inorder traversal, stop at kth visited node.
// Delete node from BST
function deleteNode(root, key) {
if (!root) return null;
if (key < root.val) { root.left = deleteNode(root.left, key); }
else if (key > root.val) { root.right = deleteNode(root.right, key); }
else {
if (!root.left) return root.right; // 0 or 1 child
if (!root.right) return root.left;
// Two children: find inorder successor (min of right subtree)
let succ = root.right;
while (succ.left) succ = succ.left;
root.val = succ.val; // copy successor's value
root.right = deleteNode(root.right, succ.val); // delete successor
}
return root;
}
// Validate BST with bounds
function isValidBST(node, min = -Infinity, max = Infinity) {
if (!node) return true;
if (node.val <= min || node.val >= max) return false;
return isValidBST(node.left, min, node.val) &&
isValidBST(node.right, node.val, max);
}- Search/insert: O(h) — go left if less, right if greater
- Validation: pass min/max bounds, each node must be strictly between them
- Kth smallest: inorder (O(h+k)) — don't need to traverse all n nodes
- Floor: largest value ≤ target — recurse right when root < target
- Ceiling: smallest value ≥ target — recurse left when root > target
Delete 3 cases: Leaf, one child, two children. For two children: inorder successor = leftmost of right subtree. Copy value, recursively delete successor (which has at most one right child).