Quick Overview
A BST keeps every left descendant below the node and every right above it. That invariant is what buys `O(log N)` lookup, and why an unbalanced tree collapses back to `O(N)`.
A Binary Tree is a non-linear data structure where each node has at most two children (left and right).
A Binary Search Tree (BST) enforces a strict ordering rule on every node:
< node.val).> node.val). 8 (Root)
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function searchBST(root, val) {
if (!root || root.val === val) return root;
// Search left if target is smaller, right if larger
return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
}
function insertBST(root, val) {
if (!root) return new TreeNode(val);
if (val < root.val) {
root.left = insertBST(root.left, val);
} else {
root.right = insertBST(root.right, val);
}
return root;
}
O(log N) time.[1, 2, 3, 4, 5]): Degenerates into a linked list with O(N) linear time!isValidBST(node, min, max).Use BSTs for ordered dictionary lookups. Next, let's explore Tree Traversals: Pre-order, In-order, and Post-order!
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.