An auction's bids are stored in a binary search tree with distinct values. Given a reserve price x, return how many bids are strictly less than x. Never visit a subtree whose values are all at least x.
Examples
50
/ \
30 70
/ \ \
20 40 80
\
25
Input: root = build_tree([50, 30, 70, 20, 40, None, 80, None, 25]), x = 45
Output: 4 (20, 25, 30, 40)
Input: root = build_tree([50, 30, 70, 20, 40, None, 80, None, 25]), x = 20
Output: 0
Constraints
0 <= number of nodes <= 3000- All values are distinct integers
- Visit only the qualifying nodes plus one search path
Goals
- Count whole subtrees at once when they are known to qualify
- Skip subtrees that cannot contain qualifying values