Binary Search Trees — Ordered Structure, Logarithmic Search

The Concept

A binary search tree (BST) is a binary tree with one extra rule that gives it tremendous power: the BST invariant.

For every node N, every key in N's left subtree is strictly less than N's key, and every key in N's right subtree is strictly greater than N's key.

This rule holds at every level — not just for a node and its immediate children, but for every ancestor. The key 5 at the root of a subtree means every key to its left is below 5 and every key to its right is above 5, no matter how deep the tree goes.

The payoff is immediate: in-order traversal (left → node → right) visits every key in ascending sorted order. A BST is, in a very real sense, a sorted list disguised as a tree.

Core Operations

Search and Insert — O(h)

Both operations walk down the tree making binary decisions at each step. At the current node, compare the target key:

• If equal, you've found it (search) or detected a duplicate (insert).
• If smaller, go left.
• If larger, go right.

Because each comparison eliminates an entire subtree, you descend at most h levels — where h is the height of the tree. For a balanced tree, h ≈ log₂ n; for a completely skewed tree (keys inserted in sorted order), h = n.

Validate a BST — O(h)

Checking each node only against its immediate parent is not sufficient. Consider a node with key 3 that is the right child of 1 and the left child of 10 — locally it looks fine, but if it were the left child of 5 it would violate the invariant two levels up.

The correct approach passes a range (low, high) down the recursion. At the root the range is (-∞, +∞). When you recurse left, the upper bound tightens to the current node's key. When you recurse right, the lower bound tightens. A node is invalid the moment its key falls outside the range it inherited.

Lowest Common Ancestor — O(h)

Given two target keys p and q, the LCA is the deepest node that is an ancestor of both. In a BST this is particularly clean: walk down from the root. If both p and q are less than the current node, the LCA is in the left subtree. If both are greater, it's in the right subtree. The moment they split to different sides — or one of them equals the current node — you've found the LCA.

Kth Smallest — O(h + k)

In-order traversal yields keys in sorted order, so the kth smallest is simply the kth node visited in an in-order walk. Implement this as a recursive descent that counts visited nodes; once the counter reaches k, record the answer and return.

Code Implementation

Complexity Analysis

For a balanced tree, h = O(log n) and all operations are logarithmic. For a skewed tree (e.g., keys inserted in sorted ascending order), h = O(n) and all operations degrade to linear. This motivates self-balancing trees (AVL, Red-Black) — but those are a separate topic.

Interactive Lab

Watch the BST guide each search query down the tree, discarding an entire subtree at every comparison.

See how each new key walks down to find its correct slot — left if smaller than the current node, right if larger — until it reaches an empty position.

The validator passes a tightening (low, high) range to every node. A node that falls outside its inherited range is highlighted as invalid.

The LCA search walks down while both targets agree on a direction; the moment they diverge (or one matches the current node), that node is the answer.

The kth-smallest traversal performs an in-order walk and counts nodes as it goes, stopping as soon as the counter reaches k.

Key Takeaways

• The ordering invariant is global, not local. Every key in the left subtree must be smaller than the root, and every key in the right subtree must be larger — not just the immediate children.
• In-order traversal = sorted output. This is a direct consequence of the invariant and is the cleanest way to extract sorted data from a BST in O(n) time.
• Performance is tied to height. All core operations are O(h). Keep the tree balanced and you get O(log n); let it skew and you pay O(n). Self-balancing trees enforce balance automatically.