The BST Ordering Property

One rule, global consequences

A binary search tree (BST) is a binary tree with a filing rule: at every node, everything in the left subtree is smaller than the node, and everything in the right subtree is larger.

Read that carefully — it says everything in the subtree, not just the immediate children. This tree breaks the rule even though every parent-child pair looks fine:

      5
     / \
    3   8
       / \
      4   9      <- 4 < 5, but 4 sits in 5's RIGHT subtree

Node 4 is greater than its parent 8's... no — 4 is less than 8, which is fine locally, but 4 lives in the right subtree of 5, where everything must exceed 5. The local check passes; the global rule fails. This distinction is exactly what Validate BST tests.

Consequence 1: O(log n) descent

The ordering means one comparison at any node discards an entire subtree: looking for 4, at node 5, go right — nothing in the left subtree can be 4. Search, insert, and delete all follow one root-to-leaf path: O(h). On a balanced tree h is about log n; that is binary search living inside a tree shape.

The fine print: only when balanced. Insert 1, 2, 3, 4, 5 in order into an empty BST and you get a right-leaning chain — h = n, and every operation degrades to O(n). Self-balancing variants (AVL, Red-Black — used by TreeMap-style ordered maps) guarantee O(log n); know they exist, but you will not implement one in an interview.

Consequence 2: inorder traversal is sorted order

Inorder (left, node, right) on a BST visits values in ascending order — the rule is "smaller things first, then me, then bigger things", applied recursively.

This unlocks Kth Smallest Element in a BST: run an inorder walk and stop at the kth visit. No sorting, no extra array — the tree is already sorted if you walk it correctly. It is also a quick sanity check anywhere: if an inorder walk of your structure is not sorted, it is not a valid BST.

Validating: pass bounds down

Because the broken tree above passes every local check, validation needs each node to respect limits inherited from all its ancestors. Pass an allowed range (lo, hi) down the tree, tightening one side at each turn:

def is_valid(node, lo=float("-inf"), hi=float("inf")):
    if not node:
        return True
    if not (lo < node.val < hi):
        return False
    return is_valid(node.left, lo, node.val) and \
           is_valid(node.right, node.val, hi)

Trace it on the broken tree: the root 5 sends its right child 8 the range (5, inf). 8 sends its left child 4 the range (5, 8). Then 4 fails 5 < 4 — caught, three levels of ancestry enforced by two numbers. This is the pass-state-down pattern from the previous lesson in its purest form. (Mind duplicates: the strict < means equal values are invalid — confirm the problem's convention.)

Consequence 3: LCA by direction

The lowest common ancestor (LCA) of two nodes is the deepest node that has both in its subtree. In a general binary tree you must search both sides. In a BST, values point the way:

• Both p and q less than the current node → LCA is in the left subtree; go left.
• Both greater → go right.
• Otherwise — they straddle the current node (or one equals it) → this node is the LCA. The paths to p and q diverge here and can never rejoin.

def lca(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root

One walk down, no recursion needed, O(h) time and O(1) space. Compare against the general-tree version you would otherwise need — the BST rule converts a two-sided search into a guided descent.

Spotting BST problems

When a problem says "BST", the ordering property is the problem. Ask which consequence it wants: guided descent (search, insert, LCA, closest value), sorted inorder (kth smallest, range sums, two-sum in a BST), or bounds (validation). If your BST solution never uses the ordering, you are solving the harder general-tree problem and leaving the whole discount on the table — usually the difference between O(n) and O(h).