Count invalid nodes in a BST
Company: Applovin
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
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.
Quick Answer: This question evaluates understanding of binary search tree invariants and the ability to identify nodes that violate ancestor-imposed value ranges, testing competency with tree data structures and constraint propagation in the coding & algorithms domain.
Given level-order binary tree values, count nodes whose value violates ancestor-implied strict BST bounds.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([5,3,7,2,4,6,8],)
Expected Output: 0
Explanation: Valid BST.
Input: ([5,1,4,None,None,3,6],)
Expected Output: 2
Explanation: Nodes in right subtree violate root bound.
Hints
- Model object-style prompts as operation streams when needed.
- Handle empty and boundary cases before the main logic.