Validate Binary Search Tree(BST) (Leetcode 98)

Hint: Writing the code according to the properties of BST takes O(n²) time. To reduce the time complexity to O(n), we update the range for each node as we traverse down the tree.

Properties of a BST:

1. The root must be greater than all the nodes of its left sub tree.

2. The root must be less than all the nodes of its right subtree.

3. Every sub tree must be a BST

Problem Link: https://leetcode.com/problems/validate-binary-search-tree/

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        
        def fun(root, lowerbound, upperbound):
        
            if(root is None):
                return True
            if(root.val<=lowerbound or root.val>=upperbound):
                return False
            lans=fun(root.left, lowerbound, root.val)
            rans=fun(root.right,root.val, upperbound)
            if(lans and rans):
                return True
            else:
                return False
                
        ans = fun(root, float('-inf'), float('inf'))
        return ans