mediumTreesPure DSA~25 min
Audit Range Sum
Audit records are indexed in a binary search tree keyed by integer timestamp. A compliance query asks for the total of all record values whose timestamp falls within an inclusive [low, high] range. Sum them without visiting irrelevant subtrees.
Problem
Given the root of a binary search tree (BST) and integers low and high, return the sum of node values whose keys are in the inclusive range [low, high].
Input
The root of a BST with n nodes (0 ≤ n ≤ 10^5), node keys distinct in [0, 10^9], and integers low ≤ high.
Output
A single integer — the sum of in-range node values.
Constraints
- 0 ≤ n ≤ 100,000
- BST property holds: left keys < node key < right keys
- Range is inclusive of both low and high
Examples
Example 1
Input
tree = [10,5,15,3,7,null,18], low = 7, high = 15
Output
32
Keys in [7,15] are 7, 10, 15 → 7 + 10 + 15 = 32.
Example 2
Input
tree = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output
23
Keys in [6,10] are 6, 7, 10 → 23.