In this guide, you will get 938. Range Sum of BST LeetCode Solution with the best time and space complexity. The solution to Range Sum of BST problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].
Example 1:
Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.
Example 2:
Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23
Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.
Constraints:
The number of nodes in the tree is in the range [1, 2 * 104].
1 <= Node.val <= 105
1 <= low <= high <= 105
All Node.val are unique.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(h)
938. Range Sum of BST LeetCode Solution in C++
class Solution {
public:
int rangeSumBST(TreeNode* root, int L, int R) {
if (root == nullptr)
return 0;
if (root->val < L)
return rangeSumBST(root->right, L, R);
if (root->val > R)
return rangeSumBST(root->left, L, R);
return root->val + rangeSumBST(root->left, L, R) +
rangeSumBST(root->right, L, R);
}
}; /* code provided by PROGIEZ */
938. Range Sum of BST LeetCode Solution in Java
class Solution {
public int rangeSumBST(TreeNode root, int L, int R) {
if (root == null)
return 0;
if (root.val < L)
return rangeSumBST(root.right, L, R);
if (root.val > R)
return rangeSumBST(root.left, L, R);
return root.val + rangeSumBST(root.left, L, R) + rangeSumBST(root.right, L, R);
}
} // code provided by PROGIEZ
