Count invalid nodes in a BST

You are given the root of a binary tree. A valid Binary Search Tree (BST) must satisfy: for every node with value v, all values in its left subtree are strictly < v, and all values in its right subtree are strictly > v (i.e., the constraint is with respect to all ancestors, not just the parent).

Instead of returning a boolean, return the number of nodes that violate the BST rule.

Input

• The root of a binary tree.
• Node values are integers.

Output

• An integer: the count of nodes that are part of at least one BST-order violation (i.e., nodes whose value is not within the valid (low, high) range implied by ancestors).

Notes / Clarifications

• Use strict inequality (no duplicates allowed in a valid BST).
• Counting is per node: if a node violates constraints from multiple ancestors, it is still counted once .

Constraints (typical interview assumptions)

• Number of nodes n up to ~ 10^5 .
• Aim for O(n) time.