98. Validate Binary Search Tree | | LeetCode Using Python

I solved the problem of validating a Binary Search Tree (BST) using Python, as seen in LeetCode problem 98. I walk through the recursive approach to ensure that each node adheres to BST properties by maintaining valid value ranges for both left and right subtrees. This method not only checks that each node’s value falls within the acceptable range but also ensures that all nodes in the subtrees follow the BST constraints. For a complete walkthrough and code implementation, check out the video below.

Python code:

# 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
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        
        #We can solve this recursively

        #Time Complexity: O(n) every node is visited once
        #Space Complexity depend on Tree: O(H) h being height. in Skewed trees it is O(n);  in balance it is O(logn)
        
        #helper function
        def is_it_valid(node, low, high):
            #Base case
            if node is None:
                return True

            #what make it False: Failing to meet valid BST Criteria
            if not((node.val > low) and (node.val < high)):
                return False

            left_subtree = is_it_valid(node.left, low, node.val)
            right_subtree = is_it_valid(node.right, node.val, high)

            return left_subtree and right_subtree #Return True if BST is Meet

        return is_it_valid(root, float('-inf'), float('inf'))
    

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