Validate Binary Search Tree

Problem Given the root of a binary tree, determine whether it is a valid BST: every node's key exceeds all keys in its left subtree and is less than all keys in its right subtree.

Input / Output

• Input: tree root. Output: boolean.

Constraints

• Up to 10^4 nodes; keys may equal INT_MIN/INT_MAX — bounds handling matters (use long/null-able bounds).

Example

• [5,1,4,null,null,3,6] → false (3 in the right subtree violates 5, though it's a valid child of 4 locally).

Expected approach

• Recursive range check: validate(node, lo, hi) — key must lie strictly inside (lo, hi); recurse left with (lo, key), right with (key, hi). O(n)/O(h). The classic wrong answer checks only parent-child pairs — the example above defeats it; be ready to show why. Alternative: inorder traversal must be strictly increasing (track previous value).