validate_bst.py

# 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):
        if not root:
            return True

        smallest, largest = float("-inf"), float("inf")
        stack = [(root, smallest, largest)]

        while stack:
            node, min_val, max_val = stack.pop()

            if not (min_val < node.val < max_val):
                return False

            stack.append((node.right, node.val, max_val)) if node.right else None
            stack.append((node.left, min_val, node.val)) if node.left else None

        return True

        # Time Complexity: O(n)
        # Space Complexity: O(h)