All problems

Count Nodes in Range of a BST

Easy · tree dfs

You are given the root of a binary search tree (BST) and two integers lo and hi, with lo <= hi. Return how many nodes hold a value v with lo <= v <= hi. Both ends of the range are included.

In a BST, for every node all values in its left subtree are smaller and all values in its right subtree are larger. All values are distinct. The bounds do not have to appear in the tree, and the tree may be empty. If no value lies in the range, return 0.

Examples

Example 1

Input: root = [10, 5, 15, 3, 7, null, 18], lo = 7, hi = 15

Output: 3

The values 7, 10 and 15 lie in [7, 15]. Both ends are counted.

Example 2

Input: root = [4, 2, 6, 1, 3, 5, 7], lo = 8, hi = 20

Output: 0

Every value is smaller than 8, so nothing lies in the range.

Example 3

Input: root = [8, 3, 10, 1, 6, null, 14], lo = 2, hi = 9

Output: 3

The values 3, 6 and 8 lie in [2, 9].

Constraints

• The number of nodes is in the range [0, 5000], and the height of the tree is at most 500.
• -10^4 <= Node.val <= 10^4, and all values are distinct.
• The tree is a valid binary search tree.
• -10^4 <= lo <= hi <= 10^4