LC 0098 [M] Validate Binary Search Tree - ALawliet/algorithms GitHub Wiki
the BST property is
L < x < R
where as you go down L, the next must have a (min, max) of (-inf, max parent)
where as you down R, the next must have a (min, max) of (min parent, +inf)
so we need a recursive function that manages (x, min, max)
class Solution(object):
def isValidBST(self, root, lo=float('-inf'), hi=float('inf')):
if not root:
return True
if not lo < root.val < hi:
return False
return self.isValidBST(root.left, lo, min(root.val, hi)) and \
self.isValidBST(root.right, max(lo, root.val), hi)