Trees and Binary Search Trees: Taxonomy, Invariant, and Traversal/Search

Problem Statement

A Binary Search Tree (BST) is defined by a strict global invariant: for any given node with key k, every node in its left subtree must have a key strictly less than k, and every node in its right subtree must have a key strictly greater than k.

You are asked to implement two functions that operate on binary trees:

1. validate_bst(root: Optional[TreeNode]) -> bool: Returns True if the tree satisfies the strict BST invariant at every node, and False otherwise.
2. find_closest_in_range(root: Optional[TreeNode], target: int, low: int, high: int) -> Optional[int]: Given the root of a valid BST, returns the key in the inclusive range [low, high] that is closest to target (i.e., minimizes abs(key - target)). If multiple keys are equidistant from target, return the smaller key. If no keys in the tree lie within [low, high], return None.

Your solution for find_closest_in_range must leverage the BST ordering property to prune subtrees that cannot contain valid candidate keys.

Interface

class TreeNode:
    def __init__(self, val: int = 0, left: 'TreeNode' = None, right: 'TreeNode' = None):
        self.val = val
        self.left = left
        self.right = right

def validate_bst(root: Optional[TreeNode]) -> bool:
    pass

def find_closest_in_range(root: Optional[TreeNode], target: int, low: int, high: int) -> Optional[int]:
    pass

Input & Output Format

• validate_bst takes the root of a binary tree and returns a boolean.
• find_closest_in_range takes the root of a verified BST and three integers (target, low, high), returning an integer or None.

Constraints

• The number of nodes n in the tree is in the range [0, 10^5].
• -10^9 <= TreeNode.val, target, low, high False`
• Explanation: The node with value 6 is in the right subtree of 10, which violates the invariant 6 > 10.

Example 2

Input Tree:
        20
       /  \
      10   30
     /  \    \
    5   15    35

• validate_bst(root) -> True
• find_closest_in_range(root, target=12, low=6, high=18) -> 10
• Explanation: The nodes within [6, 18] are 10 and 15. Distances to 12 are abs(10 - 12) = 2 and abs(15 - 12) = 3. The closest is 10.

Edge Cases

• An empty tree (root is None): validate_bst should return True; find_closest_in_range should return None.
• No nodes fall within the range [low, high].