Deleting is the one BST operation with a twist: removing a node must leave a tree that still follows the rule. First find the node (an ordinary search), then look at how many children it has. There are exactly three cases, and only the last needs any thought.
A node with two children can't just disappear — both subtrees would need a parent. Instead, replace its value with a value that can sit there without breaking the rule: the in-order successor, the smallest value in its right subtree (go right once, then left as far as possible). It's bigger than everything on the left and smaller than everything else on the right, so the rule still holds. Then delete the successor from the right subtree — and since it has no left child, that's always case 1 or 2.
Search down for the key. When it's found: with no left child, the right subtree takes its place (this also covers a leaf, whose right is null); with no right child, the left subtree does; otherwise copy the successor's value in and delete the successor from the right subtree. Each call returns the root of its (possibly changed) subtree, which the parent re-attaches.
Find the node, then handle it by how many children it has.
function deleteNode(node, key) { if (node === null) return null; // key isn't in the tree if (key < node.val) node.left = deleteNode(node.left, key); else if (key > node.val) node.right = deleteNode(node.right, key); else { if (node.left === null) return node.right; // no left child: the right takes its place if (node.right === null) return node.left; // no right child: the left takes its place let next = node.right; // two children: the successor is the while (next.left !== null) next = next.left; // smallest value in the right subtree node.val = next.val; // copy it here... node.right = deleteNode(node.right, next.val); // ...and delete it from the right } return node;}Time O(h), space O(h) for the recursion: one walk down to the node, then at most one more walk down its right subtree to the successor. (The C++ version leaks the removed node; real code would delete it.)
