938. Range Sum of BST
Explanation
To solve this problem, we can perform a depth-first search (DFS) traversal of the binary search tree (BST). At each node, we check if the node's value falls within the range [low, high]. If it does, we add the node's value to the sum. We then recursively traverse the left and right subtrees if they exist.
Algorithm:
- Initialize a variable
sumto store the total sum. - Perform a recursive DFS traversal starting from the root node.
- At each node:
- If the node's value is within the range [low, high], add the value to the
sum. - Recursively traverse the left and right subtrees if they exist.
- If the node's value is within the range [low, high], add the value to the
- Return the final
sumvalue.
Time Complexity:
The time complexity of this algorithm is O(N), where N is the number of nodes in the binary search tree. We visit each node once in the worst case.
Space Complexity:
The space complexity is O(H), where H is the height of the binary search tree. In the worst case, the recursion stack can go as deep as the height of the tree.
class Solution {
public int rangeSumBST(TreeNode root, int low, int high) {
if (root == null) {
return 0;
}
int sum = 0;
if (root.val >= low && root.val <= high) {
sum += root.val;
}
sum += rangeSumBST(root.left, low, high);
sum += rangeSumBST(root.right, low, high);
return sum;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.