Range Sum of BST

Given the root of a binary search tree and two integers low and high, return the sum of all node values between low and high inclusive. Pattern focus: BST Range Bounds. Use the BST property to ignore entire subtrees that cannot contain values in the requested range.

Input Format

root = binary tree root, low = lower bound, high = upper bound

Output Format

sum of values in [low, high]

Constraints

  • 0 <= number of nodes <= 10^5
  • -10^9 <= node values <= 10^9
  • root, low and high must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

root = [10,5,15,3,7,null,18]
low = 7
high = 15

Output:

32

Explanation:

The values 7, 10, and 15 are inside the range.

Example 2:

Input:

root = [10,5,15,3,7,null,18]
low = 6
high = 10

Output:

17

Explanation:

The values 7 and 10 are inside the range.

Loading...
Range Sum of BST - Binary Search Tree