#938
Range Sum of BST
Easy Pruned DFS
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the sum of all node values in a BST that lie in the range [low, high].
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: sum the values between low and high.
Why this works: skip whole subtrees that are out of range: below low → ignore the left side; above high → ignore the right side.
Example: 10 (5 (3, 7), 15 (-, 18)), range [7, 15]
7 + 10 + 15 = 32✦Hints open one at a time
If a node is below low, its whole left subtree is too.
If a node is above high, skip its right subtree.
↗Approach
DFS that only goes left when node.val > low and only goes right when node.val < high, adding values inside the range.
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public int rangeSumBST(TreeNode root, int low, int high) {
if (root == null) return 0;
if (root.val < low) return rangeSumBST(root.right, low, high); // left side too small
if (root.val > high) return rangeSumBST(root.left, low, high); // right side too big
return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
}
}!Common mistake
Visiting every node — correct, but it ignores the BST property.
Complexity
- Time: O(n) worst case, much less when the range is narrow.
- Space: O(h).
Topic: Binary Search Trees
🎬 Episodes 61–63: video coming soon