if key < root.key: return BST-SEARCH(root.left, key)
else: return BST-SEARCH(root.right, key)
BST-INSERT(root, key):
if root == null: return new Node(key)
if key < root.key: root.left = BST-INSERT(root.left, key)
else: root.right = BST-INSERT(root.right, key)
return root
Section 2 -- The Idea, Step by Step
Think of looking a name up in a paper phone book. You don't read every page from the front -- you open near the middle, see whether your name falls earlier or later, and throw away half the book. Then you do it again. A binary search tree (BST) freezes that habit into a shape: every value gets a spot, and from any spot the rule is always the same -- smaller things live to the left, larger things to the right.
The pieces have names. Each box is a node holding one key. The top node is the root. Every node can have a left child and a right child. The single rule that makes it a BST -- the invariant -- is that for every node, every key in its left subtree is smaller and every key in its right subtree is larger. To find a key you start at the root and compare: equal means found, smaller means step left, larger means step right. Each comparison throws away a whole subtree, exactly like tearing the phone book in half.
One worked count. Drop $n = 16$ random keys into a tree and it settles to a height of about 4. Finding any key then takes roughly 4 comparisons, while a plain unsorted list of 16 would need up to 16. The number of comparisons is just the depth of the node you land on, and the longest root-to-leaf path is the tree's height $h$ -- so every search, insert, and delete costs $O(h)$.
Now the precise picture. When keys arrive in random order the tree stays bushy: the average node sits at depth $\approx 2\ln n \approx 1.386\log_2 n$, while the height (the longest path) grows a bit faster, $\approx 4.311\ln n \approx 3\log_2 n$ -- both still $O(\log n)$. Insertion walks that same search path until it reaches an empty slot and hangs the new node there. Deleting a node with two children swaps in its in-order successor (the smallest key in its right subtree) to preserve the invariant. And reading the tree left -> node -> right -- an in-order traversal -- pours the keys out already sorted, which is why a BST is really a sorted container in disguise.
The catch is the order keys arrive in. Feed them already sorted -- $1, 2, 3, \dots$ -- and every new key is bigger than all the others, so it always goes right. The tree degenerates into a single right-leaning chain with height $h = n-1$, and search slows to $O(n)$, no better than scanning a list. That failure is exactly why self-balancing variants (AVL, red-black trees) exist: they rotate after each change to force $h = O(\log n)$ regardless of the input.
Try this with the controls above. (1) Switch the preset menu between Random and Sorted -- this single choice is what decides whether a BST stays bushy ($O(\log n)$) or collapses into a chain ($O(n)$). (2) Drag the n slider to change how many keys the structure holds, then re-read the Complexity section below to see how the height -- and therefore the search cost -- scales with $n$. (3) Step through with Next / Prev and follow the highlighted line in the BST-SEARCH / BST-INSERT pseudo-code, which spells out the "smaller goes left, larger goes right" decision made at every node.
Section 3 -- Complexity Analysis
Symbol
Meaning
n
Input size
T(n)
Time complexity function
h
Height or depth of structure
k
Key or rank parameter
W(n)
Worst-case complexity
A(n)
Average-case complexity
Step 1 -- BST Property. For every node v: all keys in left subtree < v.key, all keys in right subtree > v.key. This invariant enables O(log n) search by halving the search space at each node.
Step 2 -- Search Complexity. Best case O(1) (root is target). Average case O(log n) for random insertion order (expected height = 2 ln n ~ 1.386 log2 n). Worst case O(n) for sorted insertion -- degenerate into linked list.
Step 3 -- Insertion. Follow search path to find null position, insert new node. Cost = height of tree = O(log n) avg, O(n) worst.
Step 4 -- Deletion (3 cases). Leaf: remove directly. One child: bypass node (link parent to child). Two children: find in-order successor (leftmost node of right subtree), copy its key, delete successor recursively.
Step 5 -- In-order Traversal. Left, Root, Right. Visits all nodes in sorted order. Proof by BST property: left subtree keys < root < right subtree keys. T(n) = O(n).
Step 6 -- Expected Depth and Height. For random insertion of n distinct keys, two different averages matter. The expected depth of a node -- the typical search cost -- is 2 ln n ~ 1.386 log2 n, only ~38.6% above the optimal log2 n. The expected height (the longest root-to-leaf path) is larger, E[h] ~ 4.311 ln n ~ 3 log2 n (Devroye), and concentrates tightly around that value. Both are O(log n). But adversarial input (sorted) gives h = n-1.
Section 4 -- FAQ
What is the BST invariant? concept+
Every node satisfies: all keys in its left subtree are strictly less than the node's key, and all in right subtree are strictly greater. This enables binary search at every node.
Why does sorted insertion create worst case? concept+
Inserting 1,2,3,...,n in order: each new key is larger than all existing keys, so always goes right. Tree becomes a right-leaning chain of height n. Search degenerates to O(n) linear scan.
Where are BSTs used in production? applied+
The in-order predecessor/successor operations make BSTs ideal for: database indices (B-tree is a BST variant), C++ std::map/std::set (red-black tree), event schedulers, interval trees for geometry.
What is the expected height of a random BST? complex+
Careful: two averages get confused here. The expected node DEPTH (typical search cost) is 2 ln n ~ 1.386 log2 n, only ~38.6% above the optimal log2 n. The expected HEIGHT (longest root-to-leaf path) is larger, ~4.311 ln n ~ 3 log2 n (Devroye). Both are O(log n). However, sorted input gives h = n-1 -- hence the need for self-balancing.
How does deletion with two children work? nonobv+
Replace deleted node's key with its in-order successor (minimum key in right subtree). Then delete that successor (which has at most one child -- no left child since it is the minimum). This maintains BST property.
Can a BST be used to implement sort in O(n log n)? deep+
Yes: insert all n elements O(n log n) avg, then in-order traversal O(n). This is Tree Sort. Equivalent to Quicksort for random input -- same expected comparisons! For sorted input, degenerates to O(n^2) insertion like insertion sort on sorted data.
Section 5 -- Common Misconceptions
Conceptual Misconceptions
X BST guarantees O(log n) search.
O Only O(log n) AVERAGE for random input. Sorted input gives O(n) worst case. Use AVL or Red-Black tree for guaranteed O(log n).
X In-order traversal works on any tree.
O In-order gives sorted output ONLY if BST property holds. General trees have no ordering guarantee from in-order.
X Delete by simply setting node to null.
O Setting node to null breaks the tree if node has children. Must handle 3 cases: leaf (remove), one child (bypass), two children (successor replacement).
Implementation Errors
X Forgetting to return root after recursive insert.
O In C/Java, recursive BST insert must return the (possibly new) root pointer. Forgetting this causes silent tree corruption.
X Using iterative search but recursive insert inconsistently.
O Be consistent. Mixing recursive and iterative can cause subtle bugs in edge cases like inserting into empty tree.
X Assuming BST search is O(log n) without checking balance.
O Always verify tree height. For user input, height can be O(n). Profile or use a self-balancing variant in production.