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: . Space: .
Alternative: inorder traversal and check if values are strictly increasing.