888. Count Nodes in BST with Keys in Given Range

Given the root of a binary search tree and an inclusive range [lo, hi], count the number of nodes whose keys fall within that range. Use the BST property to prune subtrees. The input gives a level-order BST array and 'lo hi' separated by ' | '.

Input: A level-order BST array and 'lo hi', separated by ' | '.

Output: Integer — the count of in-range keys.

Examples

Input: [8,3,10,1,6,null,14] | 4 10
Output: 3
Explanation: Keys 6, 8, 10 fall within [4,10].

Input: [5] | 1 10
Output: 1
Explanation: Single key in range.

Input: [5] | 6 10
Output: 0
Explanation: No keys in range.

Constraints

• 0<=nodes<=10^4
• valid BST
• lo<=hi

Asked by