Loading
Post the reasoning, not just the code. Answers that are only a code block get collapsed.
I compared each node only against its immediate parent, which passes every shallow test I could think of. It breaks the moment a violation is more than one level deep — a node can be greater than its parent and still smaller than an ancestor it has no business being under.
Here is the version that fails. Is the fix to pass bounds down, or should I be doing an inorder walk and checking it is sorted?
Both fixes work, and they are the same idea wearing different clothes. Pass (low, high) down: the left child inherits (low, node.val), the right inherits (node.val, high). The inorder walk is that constraint unrolled — each node only needs to beat the previous value. Prefer bounds if you want O(h) space and an early exit.
Worth naming the general lesson, because it comes back in Trees Ch 03: a local check is not a tree invariant. Any time your recursion only looks at a node and its immediate children, ask what an ancestor three levels up could still ruin.
One gotcha on the inorder version: use a sentinel of negative infinity rather than None if you keep the previous value in a plain variable, or the first comparison silently short-circuits.