loading
loading
loading
loading
A tree that keeps every left descendant smaller and every right descendant larger, turning search, insert, and delete into O(log n) operations — when the tree stays balanced.
A binary search tree (BST) stores values in nodes so that, for every node, everything in its left subtree is smaller and everything in its right subtree is larger — the BST invariant. That single rule is what makes search, insert, and delete all follow the same path-from-root pattern, each taking O(height) time. When insertions arrive in a good order the tree stays roughly balanced and height is O(log n); when they arrive sorted, the tree degenerates into a linked list and height becomes O(n). Deletion is the trickiest operation: removing a node with two children requires replacing it with its in-order successor, not just unlinking it.
left and right.left, node, right) visits values in sorted order; pre-order and post-order are used for copying and deleting a tree respectively.function search(root, target) {
let node = root;
while (node !== null) {
if (target === node.value) return node;
node = target < node.value ? node.left : node.right;
}
return null; // not found
}function search(node, target) {
if (node === null) return null;
if (target === node.value) return node;
return target < node.value
? search(node.left, target)
: search(node.right, target);
}function insert(root, value) {
if (root === null) return { value, left: null, right: null };
if (value < root.value) root.left = insert(root.left, value);
else if (value > root.value) root.right = insert(root.right, value);
// else: value already present — no duplicates inserted here
return root;
}function deleteNode(root, value) {
if (root === null) return null;
if (value < root.value) { root.left = deleteNode(root.left, value); return root; }
if (value > root.value) { root.right = deleteNode(root.right, value); return root; }
// found the node to delete
if (root.left === null) return root.right;
if (root.right === null) return root.left;
// two children: replace with the in-order successor
let successor = root.right;
while (successor.left !== null) successor = successor.left;
root.value = successor.value;
root.right = deleteNode(root.right, successor.value);
return root;
}| BST (balanced) | Sorted Array | Hash Table | |
|---|---|---|---|
| Search | O(log n) | O(log n) | O(1) average |
| Insert | O(log n) | O(n) — must shift | O(1) average |
| Delete | O(log n) | O(n) — must shift | O(1) average |
| Sorted iteration | O(n) in-order traversal | O(n), already sorted | Not supported |
| Range queries ("between A and M") | O(log n + k) | O(log n + k) | Not supported — O(n) scan |
| Worst case | O(n) if degenerate | O(n) always for insert/delete | O(n) with bad hash/adversarial keys |
A sorted array gives O(log n) search but O(n) insert/delete because everything after the gap has to shift. A hash table gives O(1) average for all three but throws away order entirely — no sorted iteration, no range queries. A balanced BST is the compromise: O(log n) for search, insert, *and* delete, while still supporting min, max, in-order iteration, and range queries that a hash table simply cannot do.
Insert 10 values in sorted order and you get a tree that is really a linked list in disguise — height n, every operation O(n). Insert the same 10 values in a good order (e.g. middle-first) and height drops to about log₂(n). The BST itself does nothing to prevent degeneration; self-balancing variants (AVL, red-black trees) exist specifically to guarantee O(log n) height regardless of insertion order by rotating the tree back into balance after every insert or delete.
Deleting a leaf or a node with one child is a simple splice. Deleting a node with two children is not — you can't just remove it, since both its subtrees need a new parent. The standard fix is to copy in the value of the *in-order successor* (the leftmost node of the right subtree, guaranteed to have no left child) and then delete that successor instead, which is always one of the simple cases. Forgetting this case, or deleting the wrong node, is the single most common BST bug.
The BST invariant as stated (left < node < right) has no room for equal values. Real implementations pick a convention: reject duplicates outright, route them consistently to one side (e.g. >= goes right), or store a count/list per node. Whichever you pick, apply it consistently — mixing conventions within one tree silently breaks the invariant and makes search unreliable.
Inserting already-sorted (or reverse-sorted) data into a plain BST produces a tree where every node has only one child — structurally a linked list, with O(n) search/insert/delete and O(n) recursion depth (a real stack-overflow risk for large n). This is the concrete, common failure mode that motivates self-balancing trees in any production use of a BST.
Balanced BSTs (or their B-tree relatives) back database indexes and filesystem directories, where range queries and sorted iteration matter. Language standard libraries use them for ordered maps/sets (TreeMap in Java, std::map in C++) — you get sorted keys for free, which a hash-based map cannot offer. Compilers use them for symbol tables when scoped, ordered lookup is useful.
State the invariant precisely before coding. Handle all three delete cases explicitly — interviewers often probe specifically for the two-children case. Know the difference between a *balanced* BST (guaranteed O(log n)) and a *plain* BST (no such guarantee) and be ready to name AVL or red-black trees if asked how to guarantee balance. Validate-BST and lowest-common-ancestor are two of the most common BST interview questions — both lean directly on the invariant.
The tree degenerates into what is structurally a linked list — every node has exactly one child, height becomes O(n), and every operation slows to O(n). This is exactly what self-balancing trees (AVL, red-black) are designed to prevent.
The plain invariant doesn't define one — you must pick a convention (reject, route consistently to one side, or count per node) and apply it everywhere. Inconsistent handling silently breaks search correctness.
Either works symmetrically — the predecessor (rightmost of the left subtree) is an equally valid replacement. Codebases typically pick one convention and use it consistently; this content uses the successor.
Only for insert and delete. Search is O(log n) in both. A sorted array actually has better cache locality for search-heavy, insert-light workloads — the BST's advantage is O(log n) insert/delete instead of the array's O(n) shift.
Share what clicked for you and see notes from other learners on this topic.
Coming soon