Validate BST: Range Approach

The insight: each node must be within a valid range. As you go left, update the upper bound. As you go right, update the lower bound.

def isValidBST(root):
    return validate(root, float('-inf'), float('inf'))

def validate(node, minVal, maxVal):
    if node == null:
        return true
    if node.val <= minVal or node.val >= maxVal:
        return false
    return (validate(node.left, minVal, node.val) and
        validate(node.right, node.val, maxVal))

Going left: everything must be less than current value.

Going right: everything must be greater than current value.

Time: $O(n)$. Space: $O(h)$.

Alternative: inorder traversal and check if values are strictly increasing.