Validate Binary Search Tree

Is the tree a valid binary search tree? In a BST, for every node, all values in its left subtree are strictly smaller and all values in its right subtree are strictly larger than the node's value.

Tree format. A binary tree is given on one line in level order (top to bottom, left to right), with null for a missing child — the same way most interview platforms show trees. Trailing nulls are left out, and an empty tree is the single word null. Example: 3 9 20 null null 15 7 is

    3
   / \
  9   20
     /  \
    15   7

Input: one tree (at least one node).

Output: true or false.

Constraints: 1 ≤ nodes ≤ 10⁴, −2³¹ ≤ value ≤ 2³¹ − 1. The tree has at most 10⁴ nodes and its height is at most 500, so recursion is safe in every language.

The classic trap: checking only left.val < node.val < right.val is not enough — in 5 4 6 null null 3 7 the 3 sits in 5's right subtree. Pass down the allowed (low, high) range, or check that the inorder sequence is strictly increasing.