<gh_stars>0
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None




class Solution(object):
    def isValidBST(self, root: TreeNode) -> bool:

        def dfs(root):
            # none
            if not root:
                return True, -float('inf'), float('inf')

            if root.left is None and root.right is None:
                return True, root.val, root.val

            # check this node
            if root.left is not None and root.left.val >= root.val:
                return False, -float('inf'), float('inf')
            if root.right is not None and root.right.val <= root.val:
                return False, -float('inf'), float('inf')

            left, min_left, max_left = dfs(root.left)
            right, min_right, max_right = dfs(root.right)

            if max_left < root.val < min_right:

                if left and right:
                    min_mid = min(min_left, min_right, root.val)
                    max_mid = max(max_left, max_right, root.val)
                    return True,  min_mid, max_mid

            return False, 0, 0

        return dfs(root)[0]


l1 = TreeNode(15)
l2 = TreeNode(12)
l3 = TreeNode(-2147483648)
l1.left = l2
l1.right = l3

l4 = TreeNode(5)
l5 = TreeNode(1)
l6 = TreeNode(4)
l7 = TreeNode(3)
l8 = TreeNode(6)

l4.left = l5
l4.right = l6
l6.left = l7
l6.right = l8

l9 = TreeNode(0)
l10 = TreeNode(-1)
l9.left = l10


l11 = TreeNode(10)
l12 = TreeNode(5)
l13 = TreeNode(15)
l14 = TreeNode(6)
l15 = TreeNode(20)
l11.left = l12
l11.right = l13
l13.left = l14
l13.right = l15

sol = Solution()
print(sol.isValidBST(l9))







# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None




class Solution(object):
    def isValidBST(self, root: TreeNode) -> bool:

        def dfs(root):
            # none
            if not root:
                return True, -float('inf'), float('inf')

            if root.left is None and root.right is None:
                return True, root.val, root.val

            # check this node
            if root.left is not None and root.left.val >= root.val:
                return False, -float('inf'), float('inf')
            if root.right is not None and root.right.val <= root.val:
                return False, -float('inf'), float('inf')

            left, min_left, max_left = dfs(root.left)
            right, min_right, max_right = dfs(root.right)

            if max_left < root.val < min_right:

                if left and right:
                    min_mid = min(min_left, min_right, root.val)
                    max_mid = max(max_left, max_right, root.val)
                    return True,  min_mid, max_mid

            return False, 0, 0

        return dfs(root)[0]


l1 = TreeNode(15)
l2 = TreeNode(12)
l3 = TreeNode(-2147483648)
l1.left = l2
l1.right = l3

l4 = TreeNode(5)
l5 = TreeNode(1)
l6 = TreeNode(4)
l7 = TreeNode(3)
l8 = TreeNode(6)

l4.left = l5
l4.right = l6
l6.left = l7
l6.right = l8

l9 = TreeNode(0)
l10 = TreeNode(-1)
l9.left = l10


l11 = TreeNode(10)
l12 = TreeNode(5)
l13 = TreeNode(15)
l14 = TreeNode(6)
l15 = TreeNode(20)
l11.left = l12
l11.right = l13
l13.left = l14
l13.right = l15

sol = Solution()
print(sol.isValidBST(l9))
# Definition for a binary tree node. # none # check this node