What this module covers: Module P-4 traversed a generic binary tree, whatever shape it happened to be. This module adds one invariant — every left subtree holds smaller values, every right subtree holds larger ones — and that single rule turns a tree into a structure that supports O(log n) search, exactly like Module F-11's binary search, but over a branching structure instead of a flat array. This module covers insert, search, delete (the trickiest of the three), and how to correctly validate that the invariant actually holds.
A binary search tree enforces one rule at every single node, not just at the root: everything in the left subtree is smaller than this node's value, and everything in the right subtree is larger.
4 / \ 2 6 / \ / \ 1 3 5 7
Notice this holds recursively — not just "2 < 4 < 6" at the root, but also "1 < 2 < 3" at the node holding 2, and "5 < 6 < 7" at the node holding 6. This recursive property is exactly what makes Module P-4's inorder traversal produce sorted output: at every level, left-then-node-then-right is already the ascending order, because the invariant guarantees it.
Searching a BST follows the identical halving logic from Module F-11's binary search — at each node, one comparison rules out an entire subtree:
function search<T>(node: TreeNode<T> | null, target: T): boolean { if (node === null) return false; if (node.value === target) return true; return target < node.value ? search(node.left, target) // target must be in the left subtree, if anywhere : search(node.right, target); // target must be in the right subtree, if anywhere }
Just as Module F-11 discarded half the remaining array with each comparison, this discards an entire subtree with each comparison — if the tree is balanced (each subtree roughly half the size of its parent), this is O(log n), the same complexity class, same reasoning, now on a branching structure instead of a flat sorted array.
Inserting into a BST follows the same "compare and go left or right" logic as search — you simply keep going until you fall off the tree, then attach the new node there:
function insert<T>(node: TreeNode<T> | null, value: T): TreeNode<T> { if (node === null) return new TreeNode(value); // found the spot — attach here if (value < node.value) node.left = insert(node.left, value); else if (value > node.value) node.right = insert(node.right, value); return node; // unchanged if value already exists }
This is O(log n) on a balanced tree, for the same reason search is — but there's an important caveat worth stating plainly: a BST built by inserting already-sorted data degenerates into a straight line, not a balanced tree, because every new value is larger (or smaller) than everything already inserted, so it always attaches at the same end.
let tree: TreeNode<number> | null = null; for (const v of [1, 2, 3, 4, 5]) { tree = insert(tree, v); // every insert goes right, right, right... — a linked list in disguise } // Search is now O(n), not O(log n) — the tree has degenerated
This is the exact same shape as Module F-1's best/average/worst-case discussion: a plain BST is O(log n) on average, for reasonably random insertion order, but O(n) in the worst case. Self-balancing variants (AVL trees, Red-Black trees) exist specifically to guarantee O(log n) even in this worst case, by restructuring the tree during insertion/deletion to keep it roughly balanced — a mechanism this course doesn't implement in full, but worth knowing by name, because it's exactly what production-grade ordered structures (including the B-Trees covered in Module A-13) are built to guarantee.
Deletion is the operation that actually requires care, because removing a node must preserve the BST invariant for everything that's left. There are three distinct cases:
function deleteNode<T>(node: TreeNode<T> | null, value: T): TreeNode<T> | null { if (node === null) return null;
if (value < node.value) { node.left = deleteNode(node.left, value); } else if (value > node.value) { node.right = deleteNode(node.right, value); } else { // Found the node to delete — now handle its three possible shapes:
// Case 1: no children — just remove it if (node.left === null && node.right === null) return null;
// Case 2: one child — replace this node with its only child if (node.left === null) return node.right; if (node.right === null) return node.left;
// Case 3: two children — replace this node's value with its inorder successor // (the smallest value in the right subtree), then delete that successor from // the right subtree, where it's guaranteed to have at most one child. let successor = node.right; while (successor.left !== null) successor = successor.left; node.value = successor.value; node.right = deleteNode(node.right, successor.value); }
return node; }
Case 1 (leaf) and case 2 (one child) are straightforward — there's nothing structurally underneath to preserve. Case 3 (two children) is the interesting one: you can't just remove the node, because that would disconnect two subtrees that both need to stay attached to the tree, correctly ordered relative to each other. The fix is to find the inorder successor — the smallest value in the right subtree, found by walking left as far as possible — copy that value into the node being "deleted," and then delete the successor's original node instead (which is now guaranteed to have at most one child, since it was found by always going left, meaning it has no left child of its own). The BST invariant holds afterward because the inorder successor is, by definition, the next value up from the deleted one — exactly what should take its place.
A frequent, subtle bug: checking only that each node's immediate children satisfy left.value < node.value < right.value, without checking the invariant against the entire subtree, not just the direct child:
// BUGGY — only checks immediate children, misses violations deeper in the subtree function isValidBSTBuggy<T>(node: TreeNode<T> | null): boolean { if (node === null) return true; if (node.left && node.left.value >= node.value) return false; if (node.right && node.right.value <= node.value) return false; return isValidBSTBuggy(node.left) && isValidBSTBuggy(node.right); }
This passes a tree like { value: 5, left: { value: 3, right: { value: 6 } } } — 3 < 5 looks fine locally, and 6 > 3 looks fine locally, but 6 is in 5's left subtree, and 6 > 5, which violates the invariant against the root, not just against its immediate parent (3). The correct approach passes down a valid range that narrows as you descend, rather than only ever checking one level:
function isValidBST<T>( node: TreeNode<T> | null, min: T | null = null, max: T | null = null ): boolean { if (node === null) return true; if (min !== null && node.value <= min) return false; if (max !== null && node.value >= max) return false;
return ( isValidBST(node.left, min, node.value) && // left subtree: still bounded below by min, now also above by node.value isValidBST(node.right, node.value, max) // right subtree: now bounded below by node.value, still above by max ); }
Each recursive call carries forward the entire valid range inherited from every ancestor above it, narrowing further at each level — so a node like 6 sitting deep in 5's left subtree is correctly caught, because by the time recursion reaches it, max has already been narrowed down to 5 by an ancestor higher up, not just by its immediate parent.
Database indexes (Module A-13) are conceptually "a BST, but engineered for disk" — PostgreSQL's B-Tree indexes generalize this exact left-smaller/right-larger invariant to nodes holding many keys at once, specifically to stay shallow and balanced under the kind of adversarial (e.g., sequentially inserted) data that would degenerate a plain BST into a line.
In-memory sorted sets that need frequent insertion, deletion, and "give me the next value greater than X" queries (a real-time leaderboard, a priced order book) are natural fits for a self-balancing BST variant — the plain BST in this module is the conceptual starting point, but production code almost always reaches for a battle-tested balanced implementation rather than a hand-rolled one.
The min/max-bound validation pattern — carrying forward a narrowing valid range through recursion, rather than only checking one level — reappears any time a recursive structure has invariants that depend on ancestors, not just immediate parents (permission inheritance down a folder tree, scoping rules in nested code blocks).
A BST enforces left-smaller, right-larger at every node, recursively — the property that makes Module P-4's inorder traversal produce sorted output.
Search and insert both apply Module F-11's binary-search halving logic to a branching structure — O(log n) on a balanced tree.
A plain BST can degenerate to O(n) if data is inserted in already-sorted order, producing an unbalanced, effectively-linear tree — the reason self-balancing variants (AVL, Red-Black) and B-Trees (Module A-13) exist.
Deletion has three cases: no children (remove outright), one child (splice it in directly), two children (replace with the inorder successor, then delete the successor from its now-simpler position).
Validating a BST requires tracking a narrowing valid range through the whole recursion, not just comparing each node to its immediate children — a common and easy-to-miss bug otherwise.
The next module, Introduction to Graphs: Representation and Terminology, generalizes the tree structure one step further — where a tree has exactly one path between any two nodes, a graph allows arbitrary connections, cycles, and multiple paths.
Knowledge Check
Why does inserting the values [1, 2, 3, 4, 5] in that order into an empty BST produce a structure where search degrades to O(n), rather than the O(log n) a balanced BST would provide?
In deleteNode's "two children" case, why is the deleted node's value replaced with its inorder successor (the smallest value in its right subtree), rather than, say, its left child's value?
Why does isValidBSTBuggy incorrectly accept a tree where a node's grandchild violates the BST invariant relative to the grandparent, even though every direct parent-child comparison passes?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
Written by Jatin Jain Saraf · Architect of SupraScan