Deleting from a BST
Removing a node must keep smaller values left and bigger ones right. With no children, cut it off. With one child, the child moves up into its place. With two, copy in the next bigger value, its successor, and delete the successor instead, which always has at most one child.
This tree came from inserting the values in order. Remove 1 and keep every node's left side smaller and right side bigger.
1function remove(root, target) {2 if (root === null) return null;3 if (target < root.value) {4 root.left = remove(root.left, target);5 } else if (target > root.value) {6 root.right = remove(root.right, target);7 } else if (root.left === null) {8 return root.right;9 } else if (root.right === null) {10 return root.left;11 } else {12 let next = root.right;13 while (next.left !== null) next = next.left;14 root.value = next.value;15 root.right = remove(root.right, next.value);16 }17 return root;18}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | 1 | removing a leaf just below the root |
| average | log n | a reasonably balanced tree |
| worst | h | a chain-shaped tree makes h equal n |
| space | h | one waiting call per level |
Where it breaks
- Two children is the tricky case. Pick Two children: 3. Neither child can simply move up, because both have subtrees of their own. The successor, 4, is bigger than everything on the left and smaller than everything else on the right, so it fits exactly.
- Why the successor is easy to remove. It is the leftmost node of the right side, so it has no left child. Removing it is always one of the first two cases.
- Deleting can unbalance a tree. Always taking the successor slowly tilts a tree that sees many deletes. Balanced trees rebalance after every removal.