98. Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.

def isValidBST(root: Optional[TreeNode]):        

    def recurse(node, mini, maxi):        

        if node is None:

            return True        

        if node.val > mini and node.val < maxi:

            return  recurse(node.left, mini, node.val) \

                    and \

                    recurse(node.right, node.val, maxi)            

        return False

    return recurse(root, -math.inf, math.inf)

def isValidBST(root: TreeNode):

    if not root:

        return True

    stack = [(root, -math.inf, math.inf)]

    while stack:

        root, lower, upper = stack.pop()

        if not root:

            continue

        val = root.val

        if val <= lower or val >= upper:

            return False

        stack.append((root.right, val, upper))

        stack.append((root.left, lower, val))

    return True