98. Validate Binary Search Tree

Description:

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

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
'''
[1] recursive)

idea::
cur==current Node
to be a valid BST, the value of cur' left node should be smaller than cur node.val
and the value of cur' right node should be greaterh than cur node.val

so, required range of minimum,maximum

code::
(below)

-T/C: O(n) # need to check all nodes
-S/C: O(h)
'''
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        return self.isValid(root,-float(inf),float(inf))
    
    def isValid(self, root, minimum,maximum):
        if not root:
            return True
        
        if root.val<=minimum or root.val>=maximum:
            return False
        return self.isValid(root.left,minimum,root.val) and self.isValid(root.right,root.val,maximum)