"""
Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a 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.
    Both the left and right subtrees must also be binary search trees.

 

Example 1:

    2
   / \
  1   3

Input: [2,1,3]
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.


"""
#%%
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        return self.checkBST(root)

    def checkBST(self, node, lower=float('-inf'), upper=float('inf')):
        if not node:
            return True
        if node.val <= lower or node.val >= upper:
            return False
        if not self.checkBST(node.left, lower, node.val):
            return False
        if not self.checkBST(node.right, node.val, upper):
            return False
        return True

solution = Solution()

#     2
#    / \
#   1   3
tree = TreeNode(2)
tree.left = TreeNode(1)
tree.right = TreeNode(3)
print(solution.isValidBST(tree)) # True


#     5
#    / \
#   1   4
#      / \
#     3   6
tree = TreeNode(5)
tree.left = TreeNode(1)
tree.right = TreeNode(4)
tree.right.left = TreeNode(3)
tree.right.right = TreeNode(6)
print(solution.isValidBST(tree)) # False


#%%
