Trees & binary search trees
Nodes, children, and the ordering invariant that makes a BST searchable in O(log n). · 8 min read
A tree is a hierarchy of nodes: a single root at the top, each node holding children below it, with no cycles. A binary tree limits each node to at most two children — a left and a right.
A binary search tree (BST) adds one rule, the ordering invariant: for every node, everything in its left subtree is smaller, and everything in its right subtree is larger. That rule is what makes it searchable. Watch it being built:
Interactive visualization: Building a BST by inserting values — step through it frame by frame on this page.
To insert (or search), you start at the root and go left if smaller, right if larger, repeating until you find the value or reach an empty spot. Each step discards a whole subtree — the same halving we saw in binary search.
Why balanced height is logarithmic
level 0 holds 1 node— The root.level 1 holds up to 2 nodes— Each node has two children.level 2 holds up to 4 nodes— Capacity doubles each level.levels 0..h hold about 2ʰ nodes— A balanced binary tree fills exponentially.2ʰ ≈ n ⟹ h ≈ log₂ n— Solve for height.
Result: O(log n) height when balanced