Validate Binary Search Tree

Implement binarySearchTreeValidate(root) — return true if the binary tree rooted at root is a valid binary search tree (BST), and false otherwise. A BST is a tree where every node's value is greater than every value in its left subtree and less than every value in its right subtree. That whole-subtree ordering is what lets you find, insert, and delete a value in O(height) time instead of scanning every node — it's the invariant behind ordered maps and sets in many standard libraries.

Signature

// A tree node:
//   { val: number, left: Node | null, right: Node | null }
// root: Node | null — the root of the tree, or null for an empty tree.
// returns: boolean — true if the tree is a valid BST, false otherwise.
function binarySearchTreeValidate(root): boolean;

A leaf is a node whose left and right are both null. An empty tree is root === null.

Examples

// A valid BST: every left descendant < its ancestor < every right descendant.
//        5
//       / \
//      3   8
//     / \
//    1   4
const valid = {
  val: 5,
  left:  { val: 3, left: { val: 1, left: null, right: null },
                   right: { val: 4, left: null, right: null } },
  right: { val: 8, left: null, right: null },
};
binarySearchTreeValidate(valid); // → true

// NOT a BST, even though each node looks fine next to its own children.
//      5
//       \
//        7
//       /
//      4   ← 4 sits in 5's RIGHT subtree, but 4 < 5
const sneaky = {
  val: 5,
  left: null,
  right: { val: 7, left: { val: 4, left: null, right: null }, right: null },
};
binarySearchTreeValidate(sneaky); // → false

In the second tree, 7 > 5 (good as 5's right child) and 4 < 7 (good as 7's left child). Every parent–child pair is locally ordered. But 4 lives somewhere in 5's right subtree, and the BST rule says everything there must exceed 5. It doesn't. So the tree is invalid — a fact you cannot see by only comparing a node to its immediate children.

Notes

• Inequalities are strict; duplicates are invalid. A node must be strictly greater than its left subtree and strictly less than its right subtree. A child equal to its parent ({ val: 5, left: { val: 5, ... } }) makes the tree invalid here. (Some definitions allow duplicates on one side — we don't; treat equal values as a violation.)
• The constraint spans the whole subtree, not just children. A node bounds all of its descendants, not only its two children. The second example fails on exactly this point.
• An empty tree is a valid BST. binarySearchTreeValidate(null) returns true.
• A single node is a valid BST. A lone node with no children has nothing to violate, so it returns true.
• Values are finite numbers. You don't need to handle NaN, non-numeric values, cycles, or parent pointers — the input is always a finite binary tree of numbers.