Coding questions · Applovin
Count invalid nodes in a BST
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.
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
nup to ~10^5. - Aim for
O(n)time.
Count Invalid Nodes in a BST
Examples
Example 1
Input: ([5,3,7,2,4,6,8],)
Output: 0
Explanation: Valid BST.
Example 2
Input: ([5,1,4,None,None,3,6],)
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.