Count BST Nodes in a Range

Given a binary search tree root, and integers lo and hi, return the count of all nodes in root whose values are between [lo, hi] (inclusive).

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Count-BST-Nodes-in-a-Range

Examples

Example 1

Input

• root =

• lo = 5
• hi = 10

Output

• answer = 3

Explanation

Only 7, 8, 9 are between [5, 10].

Solution