Solutions

# Check boundaries recursively or iteratively with DFS or BFS.
# trees

# Recursive DFS - O(n) time, O(n) space
def isValidBST(root: TreeNode | None) -> bool:
    return is_valid(root, -99999999999, +999999999999)


def is_valid(node: TreeNode | None, left: int, right: int) -> bool: 
    if not node:
        return True

    return left < node.val < right and \
            is_valid(node.left, left, node.val) and \
            is_valid(node.right, node.val, right)


# Iterative DFS - O(n) time, O(n) space
def isValidBST(root: TreeNode | None) -> bool:
    stack = [(root, -99999999999, +999999999999)]

    while stack:
        node, left, right = stack.pop()

        if not node:
            continue

        if not (left < node.val < right):
            return False

        stack.append((node.left, left, node.val))
        stack.append((node.right, node.val, right))

    return True


# Iterative BFS - O(n) time, O(n) space
def isValidBST(root: TreeNode | None) -> bool:
    queue = [(root, -99999999999, +999999999999)]

    while queue:
        node, left, right = queue.pop(0)

        if not node:
            continue

        if not (left < node.val < right):
            return False

        queue.append((node.left, left, node.val))
        queue.append((node.right, node.val, right))
    return True