BST Insert, Search & Delete
You'll learn to
- -Implement BST insert and search using the invariant from the last chapter
- -Enumerate the three cases for BST delete
- -Use the in-order successor to correctly delete a node with two children
Insert and search on a BST are both direct consequences of the invariant: at each node, decide whether to go left or right by comparing against the target value, and recurse. Delete is the operation that actually earns its reputation as the trickiest part of this whole tier - not because any single case is hard, but because there are three distinct cases, and getting the third one wrong is the single most common BST bug people write.
Insert
To insert a new value, walk down from the root the same way you would search for it - left if smaller, right if larger - until you fall off the tree (hit a `None`). That empty spot is exactly where the new node belongs, since it is guaranteed to preserve the invariant at every node along the path you walked.
Search
Delete: Three Cases
Deleting a node is easy in two of its three cases and genuinely subtle in the third:
- -No children (a leaf): simply remove it - return None to the parent in its place.
- -One child: the node is redundant - splice it out by returning its single child directly to the parent.
- -Two children: neither child can just take the node's place without breaking the invariant for one side or the other. Instead, find the in-order successor - the smallest value in the right subtree (reached by walking left as far as possible from `node.right`) - copy that value into the node being "deleted," then recursively delete the successor from the right subtree, where it is now guaranteed to have at most one child.
Why the in-order successor specifically? It is the smallest value greater than the node being deleted, so promoting it preserves the invariant on both sides: everything in the original left subtree stays smaller than it, and everything remaining in the right subtree stays larger. And because it was the leftmost node in the right subtree, it can have at most a right child of its own - so deleting it from its original spot is guaranteed to only ever hit Case 1 or Case 2, never Case 3 again.
When deleting a BST node that has two children, why can't you just promote its left child to take its place?
Level 63: Binary Search Tree from Scratch asks you to build exactly this BST class - insert, search, delete (including the two-children case above using the in-order successor), and inorder.