Binary Search Trees: Ordered Structure, O(log n) When Balanced
The ordering invariant that makes search, insertion, and deletion O(log n) on average — and the honest reason that guarantee can quietly collapse to O(n).
What you'll learn
- State and apply the binary search tree ordering invariant
- Implement search and insertion into a BST recursively
- Explain why an unbalanced BST degrades from O(log n) toward O(n)
Prerequisites
Explanation
A binary search tree (BST) is a binary tree with one additional rule, the ordering invariant: for every node, every value in its left subtree is smaller, and every value in its right subtree is larger (this course assumes no duplicate values, to keep the invariant unambiguous). This single rule is what turns a tree from "a shape" into "a shape you can search efficiently" — at every node during a search, comparing the target to the current node's value tells you which entire subtree to discard, exactly the way binary search over a sorted array works (covered in the next module), except the tree's shape is the sorted structure, rather than a separate sorted array you search over.
Search starts at the root and, at each node, compares the target to the current value: equal means found; smaller means recurse left (everything in the right subtree is provably too large to bother checking); larger means recurse right. Insertion follows the identical comparison logic down to where the value would be found, then attaches a new leaf node there instead of finding a match. Both operations, in a balanced tree — one whose height stays proportional to log n rather than growing toward n — take O( ext{height}) = O(log n), because each comparison eliminates roughly half the remaining nodes from consideration, mirroring binary search's halving.
The honest caveat, worth stating precisely rather than glossing over: a BST's height is only O(log n) if the tree stays reasonably balanced — and a plain BST, as taught in this lesson, does not guarantee that on its own. Inserting already-sorted data (1, 2, 3, 4, 5, in that order) into a plain BST produces a tree that's really just a linked list in disguise — every node has only a right child, height n - 1, and search degrades to genuinely O(n), the exact same worst case as a linear scan. Self-balancing trees (AVL trees, red-black trees) solve this by actively restructuring themselves during insertion/deletion to guarantee O(log n) height regardless of insertion order — a real, important technique, but implementing one is beyond this foundational lesson's scope; the key, honest takeaway here is knowing that the problem exists and why, which is what lets you recognize when a plain BST's average-case guarantee doesn't actually apply to your data's insertion order.
Example
BST search and insertion, both O(height) via the ordering invariant -- plus the pathological case that breaks the O(log n) assumption.
function makeNode(value, left = null, right = null) {
return { value, left, right };
}
function bstInsert(node, value) {
if (node === null) return makeNode(value);
if (value < node.value) node.left = bstInsert(node.left, value);
else if (value > node.value) node.right = bstInsert(node.right, value);
return node; // value === node.value: no duplicates, tree unchanged
}
function bstSearch(node, target) {
if (node === null) return false;
if (target === node.value) return true;
return target < node.value ? bstSearch(node.left, target) : bstSearch(node.right, target);
}
let balanced = null;
for (const v of [8, 3, 10, 1, 6]) balanced = bstInsert(balanced, v);
console.log(bstSearch(balanced, 6)); // true -- found in a couple of hops, height stays small
let degenerate = null;
for (const v of [1, 2, 3, 4, 5]) degenerate = bstInsert(degenerate, v); // already-sorted input!
// degenerate is now effectively a linked list: 1 -> 2 -> 3 -> 4 -> 5, all right children.
// bstSearch(degenerate, 5) must walk all 5 nodes -- O(n), not O(log n).Try it yourself
Insert [5,3,8,1,4,7,9] (a better-balanced order) and compare how many comparisons bstSearch needs for the same target value.
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Guided exercise
Guided exercise
Write findMin(node) that returns the smallest value in a BST (throw an Error if the tree is empty). Use the ordering invariant directly: the minimum is always the leftmost node -- no comparisons against other values needed.
Checks: finds the minimum in a multi-level tree · a single-node tree's minimum is itself · throws on an empty tree
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Independent exercise
Independent exercise
Write isValidBst(node) that checks whether a binary tree actually satisfies the BST ordering invariant EVERYWHERE, not just locally between immediate parent/child (a tree can look locally fine at every single node and still violate the invariant globally -- construct a counterexample to test this if you're unsure). Use a min/max bound that narrows as you recurse.
Checks: accepts a genuinely valid BST · an empty tree is valid · rejects a tree that's locally plausible but globally violates the invariant · a single node is trivially valid
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Common mistakes
- Validating a BST by only comparing each node to its immediate parent -- this misses violations where a deeper descendant breaks the invariant relative to an ANCESTOR further up, not just its direct parent.
- Assuming any BST automatically gives O(log n) operations -- this only holds for a reasonably balanced tree; inserting already-sorted data into a plain BST produces a degenerate, linked-list-shaped tree with O(n) operations.
- Forgetting the strict inequality in the ordering invariant when duplicates are disallowed -- using <= / >= instead of < / > for the bounds check can silently accept an invalid tree containing an equal value in the wrong position.
Knowledge check
Takeaway
A BST's O(log n) search and insertion come from the ordering invariant letting each comparison discard an entire subtree — but that guarantee depends entirely on the tree staying balanced, which a plain BST does not enforce on its own; sorted-order insertion is the classic case that silently degrades it to O(n).
Summary
A BST requires every left subtree to hold smaller values and every right subtree larger values. Search and insertion are O(height), which is O(log n) only when the tree is reasonably balanced. A plain BST does not self-balance — self-balancing variants (AVL, red-black trees) exist specifically to guarantee O(log n) regardless of insertion order.
References
Your notes
Notes save automatically.
Finished this lesson?
Mark it complete to track your progress and schedule a future review.
AI tutor
The optional AI tutor isn't enabled in this deployment. All lessons, exercises, quizzes, and search work fully without it.