Range Sum of BST
In many applications, such as database indexing or financial data analysis, efficiently querying data within a specific range is crucial. Binary Search Trees (BSTs) are fundamental data structures that can support such range queries effectively. This problem assesses your ability to leverage the inherent properties of a BST to efficiently compute the sum of node values within a given numerical range.
Your task is to implement a function rangeSumBST that takes the root of a Binary Search Tree (BST) and two integers, low and high, as input. The function should return the sum of all node values (Node.val) such that low <= Node.val <= high.
To achieve optimal performance, your solution should make effective use of the BST properties to avoid unnecessary traversals of subtrees that cannot possibly contain values within the specified range.
Function Signature:
function rangeSumBST(root: TreeNode | null, low: number, high: number): number;
Input:
root: A TreeNode representing the root of a Binary Search Tree. If the tree is empty, root will be null.low: An integer representing the inclusive lower bound of the desired range.high: An integer representing the inclusive upper bound of the desired range.Output:
[low, high] range (inclusive).root is null (an empty tree), the sum should be 0.[low, high] is always valid, meaning low <= high.Node.val are unique integers.Examples
Example 1
Input:
root = [10,5,15,3,7,null,18], low = 7, high = 15
Output:
32
Note:
Nodes with values 7, 10, and 15 are within the range [7, 15]. Their sum is 7 + 10 + 15 = 32.
Example 2
Input:
root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output:
23
Note:
Nodes with values 6, 7, and 10 are within the range [6, 10]. Their sum is 6 + 7 + 10 = 23.
Example 3
Input:
root = [1,2,3], low = 10, high = 20
Output:
0
Note:
No nodes in the tree have values within the range [10, 20].
Constraints
[0, 10^4].Node.val is an integer in the range [0, 10^5].low and high are integers in the range [0, 10^5].low <= high.root not being a valid BST, low > high).Loading editor...