Search trees: one rule, and everything that follows from it

The rule#

For every node: everything in its left subtree is smaller, everything in its right subtree is larger.

That word "everything" is the whole subject. Say it as "the left child is smaller" and you have a different, weaker rule that most broken search trees also satisfy.

What the rule buys you#

Searching becomes binary search. Compare with the node: equal and you are done, smaller and the entire right subtree is ruled out, larger and the entire left one is. Each comparison halves what is left, so a balanced tree of a million nodes needs about twenty steps.

"Rules out an entire subtree without looking at it" is the same move as binary search on a sorted array. The tree is that array with the comparisons built into the shape.

The one fact that solves half the problems#

An inorder walk visits the values in increasing order.

It follows directly: left is smaller, right is larger, so left-me-right is sorted. Once you have this:

• kth smallest is walk inorder and count.
• validate a search tree is walk inorder and check each value beats the last.
• sum of values in a range is walk inorder and add while you are inside it.
• inorder successor is the next node in that walk.

Four problems, one walk.

The trap, and it catches everyone#

Checking a node against its two children is not enough:

      5
     / \
    1   4
       / \
      3   6

Every node beats its own children. The tree is still wrong: the 3 is in the right subtree of the 5, and 3 is less than 5. Searching for 3 would go right at the root and never find it.

The fix is to carry the allowed range down. The root may be anything; going left tightens the ceiling to the node's value, going right raises the floor. A node must sit strictly inside the range every ancestor allows, not just its parent.

Balance, and why it is not free#

Everything above assumed the tree is roughly balanced. Nothing enforces that. Insert 1, 2, 3, 4, 5 into an empty search tree in that order and you get a straight line to the right: a linked list with extra pointers, where search costs n instead of log n.

Real systems use self-balancing variants, red-black and AVL trees, which rotate after inserts to keep the height down. Your language's sorted map is one of those. You will almost never implement the rotations, and you should know why they exist: without them the worst case is the sorted input, which is also the most likely input.

Practice in order#

1. Binary search on an array, so the halving idea is already yours.
2. Validate a search tree, which is where the range trap lives.
3. The kth smallest value, which is inorder-is-sorted made concrete.