The machine must decide whether a binary tree satisfies the BST invariant: every node's value is strictly greater than everything in its left subtree and strictly less than everything in its right subtree. The classic trap is that checking only against the immediate parent is not enough — a node deep in the left subtree must still be smaller than its great-grandparent.
The key insight is to pass a valid range down the recursion. When the machine descends into the left child, it tightens the upper bound to the current node's value; when it descends into the right child, it raises the lower bound. If any node falls outside its inherited range, the tree is invalid.
The approach has three steps. First, initialize the recursion with an unbounded range, negative and positive infinity. Second, at each node, check that its value is strictly between the inherited bounds — the check must use strict inequalities since equal values are invalid in a BST. Third, recurse left with the new upper bound and right with the new lower bound. Each node is visited once, so time is O(n) and space is O(h) for the stack.
The trickiest edge case is values at the integer extremes: the machine cannot use infinity sentinels that fit in 32-bit ints when node values can equal INT_MIN or INT_MAX. Using Python's None or float('inf') bounds avoids the overflow trap that bites languages with fixed-width integers.
def isValidBST(root, lo=float('-inf'), hi=float('inf')):
if not root:
return True
if not (lo < root.val < hi):
return False
return isValidBST(root.left, lo, root.val) and isValidBST(root.right, root.val, hi)