560. Range Sum of BST
Your function receives the root of a binary search tree and two integers, low and high. It returns the sum of the values of every node that falls inside the inclusive range [low, high].
Remember what makes a BST special: at every node, everything in the left subtree is smaller and everything in the right subtree is larger (all values here are unique). That ordering is a gift — whole subtrees can be ruled in or out without ever visiting them.
Example 1:
Input: root = [12, 6, 20, 3, 9, 15, 25], low = 9, high = 20
Output: 56
Explanation: The nodes with values in [9, 20] are 12, 9, 15 and 20. Their sum is 56; the nodes 6, 3 and 25 fall outside the range.
Example 2:
Input: root = [8, 4, 11, 2, 6, null, 14, null, null, 5], low = 5, high = 11
Output: 30
Explanation: In-range values are 8, 11, 6 and 5, which add to 30. The values 4, 2 and 14 are excluded.
Constraints:
- 1 ≤ number of nodes ≤ 2 * 10⁴
- 1 ≤ node.val ≤ 10⁵
- 1 ≤ low ≤ high ≤ 10⁵
- All node values are unique.
Hints:
Start simple: any traversal that touches every node can test each value against [low, high] and add the ones that qualify.
Now use the BST property. If a node's value is below low, can anything in its left subtree possibly be in range?
If node.val < low, skip the whole left subtree; if node.val > high, skip the whole right subtree. Recurse only where the range can still live.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [12, 6, 20, 3, 9, 15, 25], low = 9, high = 20
Expected output: 56