Range Sum of Transaction IDs in BST
At Stripe, efficiently managing and querying transaction data is paramount. Transaction IDs are often numerical and can be structured in a way that allows for quick lookups and aggregations. This problem asks you to leverage the properties of a Binary Search Tree (BST) to quickly sum up transaction IDs that fall within a specified range, mimicking a common reporting or auditing requirement.
Given the root of a Binary Search Tree (BST) where each node's val represents a unique transaction ID, and two integers, lowId and highId, your task is to return the sum of all transaction IDs in the BST that are within the inclusive range [lowId, highId].
Input:
root: The root node of a Binary Search Tree. Each node has a val (number), left (TreeNode | null), and right (TreeNode | null).lowId: An integer representing the lower bound of the inclusive range.highId: An integer representing the upper bound of the inclusive range.Output:
lowId and less than or equal to highId.lowId will always be less than or equal to highId.0.Examples
Example 1
Input:
root = [10,5,15,3,7,null,18], lowId = 7, highId = 15
Output:
32
Note:
The transaction IDs in the tree are [3, 5, 7, 10, 15, 18]. IDs within the range [7, 15] are 7, 10, 15. Their sum is 7 + 10 + 15 = 32.
Example 2
Input:
root = [10,5,15,3,7,13,18,1,null,6], lowId = 6, highId = 10
Output:
23
Note:
The transaction IDs are [1, 3, 5, 6, 7, 10, 13, 15, 18]. IDs within the range [6, 10] are 6, 7, 10. Their sum is 6 + 7 + 10 = 23.
Example 3
Input:
root = [10,5,15,3,7,null,18], lowId = 20, highId = 25
Output:
0
Note:
No transaction IDs in the tree are within the range [20, 25].
Constraints
0 and 10^4.val (transaction ID) will be between 0 and 10^5.lowId and highId will be between 0 and 10^5.Loading editor...