Lesson 23 — Validate a BST

Validate a BST with allowed ranges

It is not enough that each child is on the correct side of its parent: in a BST every node must fit the rule for all its ancestors. So pass down an allowed range (lo, hi). Going left, the node's value becomes the new upper bound; going right, the new lower bound.

#      5
#     / #    3   8
#       /
#      4    <- 4 < 8 is fine locally, but 4 < 5 breaks the rule

Why it matters: checking an invariant (a rule that must always hold) is how you catch subtle bugs in data structures before they corrupt data.