Range Sum of BST
Problem
Given the root of a BST and integers low and high, return the sum of all node values v with low ≤ v ≤ high.
tree=[10,5,15,3,7,null,18], low=7, high=1532def rangeSumBST(root, low, high):
if not root: return 0
if root.val < low: return rangeSumBST(root.right, low, high)
if root.val > high: return rangeSumBST(root.left, low, high)
return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high)function rangeSumBST(root, low, high) {
if (!root) return 0;
if (root.val < low) return rangeSumBST(root.right, low, high);
if (root.val > high) return rangeSumBST(root.left, low, high);
return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
}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);
if (root.val > high) return rangeSumBST(root.left, low, high);
return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
}
}int rangeSumBST(TreeNode* root, int low, int high) {
if (!root) return 0;
if (root->val < low) return rangeSumBST(root->right, low, high);
if (root->val > high) return rangeSumBST(root->left, low, high);
return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);
}Explanation
We want the sum of all values inside [low, high]. The naive way visits every node, but a BST lets us skip whole branches we know can't help — that's the real speedup here.
The recursion uses the ordering property: everything in a node's left subtree is smaller, everything on the right is larger. So if root.val < low, the entire left subtree is too small — we ignore it and only recurse right. If root.val > high, the right subtree is too big — we recurse left only.
When the node's value is inside the range, we add it and recurse into both children, since both sides might contain more in-range values.
Example: tree [10, 5, 15, 3, 7, null, 18], range [7, 15]. At 10 (in range) we add 10 and go both ways. Node 5 is below 7, so we skip its left child 3 and only check 7 (add it). Node 15 is in range (add it); its child 18 is above 15 so it's pruned. Total = 10 + 7 + 15 = 32.
By pruning out-of-range subtrees, we often touch far fewer than all nodes, which is why this beats a blind full traversal.