Validate Binary Search Tree

Problem

Given the root of a binary tree, decide whether it is a valid binary search tree. A valid BST requires, for every node, that every value in its left subtree is strictly less than the node's value and every value in its right subtree is strictly greater, and that both subtrees are themselves valid BSTs. Return True or False.

• The tree has between 1 and 40,000 nodes.
• Node values are signed 32-bit integers, so the extreme values -2^31 and 2^31 - 1 can appear as node values (this matters for how bounds are represented).

Examples

• root = [8, 3, 12] → True. Left smaller, right larger, nothing deeper to check.
• root = [10, 4, 9, None, None, 7, 11] → False. The right child 9 is smaller than the root 10.
• root = [10, 6, 14, None, None, 5, 16] → False. The node 5 is smaller than its parent 14, which is fine locally, but it sits in the right subtree of 10, so it must be greater than 10.

Hints

1. Checking each node only against its parent passes the second example and fails the third. What constraint does a grandparent impose?
2. As you walk down, every left turn puts an upper bound on everything below, and every right turn puts a lower bound. How many bounds do you actually need to carry?
3. Pass an open interval (low, high) down the recursion; alternatively, an inorder traversal of a BST must be strictly increasing.