All problems

Range Sum of BST

Easy · tree dfs

You are given the root of a binary search tree (BST) and two integers low and high, with low <= high. In a BST, every value in a node's left subtree is smaller than the node's own value, every value in its right subtree is larger, and no value appears twice.

Return the sum of the values of all nodes whose value v satisfies low <= v <= high. Both ends of the range count. 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 = [12, 6, 20, 3, 9, 15, 25], low = 6, high = 15

Output: 42

The values 6, 9, 12 and 15 lie in [6, 15], and 6 + 9 + 12 + 15 = 42.

Example 2

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

Output: 0

Every value is smaller than 8, so nothing is added.

Example 3

Input: root = [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13], low = 5, high = 11

Output: 31

The values 6, 7, 8 and 10 lie in [5, 11].

Constraints

• The number of nodes is in the range [0, 5000], and the height of the tree is at most 1000.
• 1 <= Node.val <= 10^5, and all values are distinct.
• The tree is a valid binary search tree.
• 1 <= low <= high <= 10^5