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.
class BST:
def __init__(self):
self.root = None
def insert(self, value):
self.root = self._insert(self.root, value)
def _insert(self, node, value):
if node is None:
return TreeNode(value)
if value < node.value:
node.left = self._insert(node.left, value)
elif value > node.value:
node.right = self._insert(node.right, value)
return node # duplicates are silently ignoredSearch
def search(self, value):
return self._search(self.root, value)
def _search(self, node, value):
if node is None:
return False
if value == node.value:
return True
if value < node.value:
return self._search(node.left, value)
return self._search(node.right, value)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.
Interview Signal is part of Pro
See a real weak answer next to a real strong one for this exact topic.
Quiz is part of Pro
Test what you just read with a short quiz, and bank the XP.
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.