Range Sum of a BST
Sum every node value in a binary search tree that falls within a given inclusive range.
Given the root of a binary search tree (BST) and two integers low and high, return the sum of every node's value that lies within the inclusive range [low, high].
Example 1
Input: root = [5,3,8,2,4,7,9], low = 3, high = 8
Output: 27
Explanation: The in-range values are 3, 4, 5, 7, and 8 (2 and 9 fall outside [3, 8]); 3 + 4 + 5 + 7 + 8 = 27.
Example 2
Input: root = [5,3,8,2,4,7,9], low = 6, high = 6
Output: 0
Explanation: No node has value 6.
Example 3
Input: root = [5], low = 1, high = 10
Output: 5
Constraints
- The number of nodes in the tree is in the range [0, 20000].
- 1 <= Node.val <= 100000
- 1 <= low <= high <= 100000
- root is guaranteed to be a valid binary search tree.
- All node values are unique.
Follow-up
How does the pruning strategy change the running time for a very wide tree when [low, high] only covers a small slice of the value range?
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.