validate_binary_search_tree.py

from typing import Optional


class TreeNode:
    """LeetCode provides this class; repeated here so the file runs standalone."""

    def __init__(self, val: int = 0, left: "Optional[TreeNode]" = None,
                 right: "Optional[TreeNode]" = None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """LeetCode #98 - Validate Binary Search Tree (Medium)
    https://leetcode.com/problems/validate-binary-search-tree/

    A valid BST requires that *every* node in the left subtree is smaller than
    the node, and every node in the right subtree is larger - not just the
    immediate children.
    """

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        """Carry an allowed (low, high) range down the tree.

        Key insight - and the trap this problem is built around: checking only
        `node.left.val < node.val < node.right.val` is wrong. Consider

                5
               / \\
              1   6
                 / \\
                3   7

        Every parent/child pair looks fine, yet 3 sits in the right subtree of 5
        and breaks the BST property globally.

        The fix is to pass down the interval a node is allowed to live in.
        Going left tightens the upper bound to the parent's value; going right
        tightens the lower bound. A node is valid when it falls strictly inside
        its inherited range - which encodes *every* ancestor's constraint, not
        just the parent's.

        Infinities seed the root's range so it accepts any value.

        Time:  O(n) - each node is checked once.
        Space: O(h) - recursion depth.
        """
        def valid(node: Optional[TreeNode], low: float, high: float) -> bool:
            if node is None:
                return True                       # empty subtree is a valid BST

            if not (low < node.val < high):
                return False

            return (valid(node.left, low, node.val)      # left: cap at node.val
                    and valid(node.right, node.val, high))  # right: floor at node.val

        return valid(root, float("-inf"), float("inf"))

        # Alternative worth naming in an interview: an in-order traversal of a
        # BST must produce a strictly increasing sequence, so walking in-order
        # and comparing with the previous value works too.