The four traversals, animated

The invariant people remember is 'left is smaller, right is bigger'. That is true, and it is not the whole rule.

The real invariant is about subtrees, not children. Every node in the left subtree — not just the left child — must be smaller.

Which means a local check can never validate a tree. Let me show you the counterexample everybody writes first.

Here is the fix. Instead of comparing to the parent, we carry a range down: low and high.

The root gets negative infinity to positive infinity. The left child inherits the same low but a new high.