leetcode-98 Validate Binary Search Tree

# Given the root of a binary tree, determine if it is a valid 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 contains only nodes with keys greater than the node's key.
# - Both left and right subtrees must also be BSTs.
#
# Example 1:
# Input: root = [2,1,3]
# Output: true
#
# Example 2:
# Input: root = [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.
#
# Constraints:
# The number of nodes in the tree is in the range [1, 10^4].
# -2^31 <= Node.val <= 2^31 - 1

# 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:
    # Approach 1: Recursive with Range Constraints
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def validate(node, min_val, max_val):
            if not node:
                return True

            # Check if current node violates BST property
            if node.val <= min_val or node.val >= max_val:
                return False

            # Recursively validate left and right subtrees
            # Left: all values must be < node.val
            # Right: all values must be > node.val
            return (validate(node.left, min_val, node.val) and
                    validate(node.right, node.val, max_val))

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

    # Approach 2: Inorder Traversal (should be sorted)
    def isValidBST2(self, root: Optional[TreeNode]) -> bool:
        # Inorder traversal of BST should produce sorted sequence
        self.prev = None

        def inorder(node):
            if not node:
                return True

            # Check left subtree
            if not inorder(node.left):
                return False

            # Check current node
            if self.prev is not None and node.val <= self.prev:
                return False
            self.prev = node.val

            # Check right subtree
            return inorder(node.right)

        return inorder(root)

# Time Complexity: O(n) - visit each node once
# Space Complexity: O(h) - recursion stack, h is height
#
# Key Insight: Pass valid range constraints down the tree,
# not just comparing with immediate parent