Range Sum of BST Easy 0 attempts
LeetCode ↗

Range Sum of BST

Easy TreeBinary TreeDFS LeetCode

You're given the root of a binary search tree along with two bounds, low and high. Add up the values of every node that falls within that range, inclusive on both ends.

Input Format
Implement rangeSumBST(root, low, high). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
root = [10,5,15,3,7,null,18]
low = 7
high = 15
Output
32

Example 2

Input
root = [1]
low = 2
high = 3
Output
0
Constraints
  • 1 <= number of nodes <= 2 * 10^4
  • 1 <= Node.val <= 10^5
  • 1 <= low <= high <= 10^5
Test Cases (2)
Case 1
Args: [[10,5,15,3,7,null,18],7,15] Expected: 32
Case 2
Args: [[1],2,3] Expected: 0
Topics
TreeBinary TreeDFS

Pruned Iterative DFS

Add values inside the inclusive range. The BST ordering lets us omit branches that cannot contain a qualifying value.

javascript
function rangeSumBST(root, low, high) {
  const stack=root?[root]:[];let sum=0;
  while(stack.length){const node=stack.pop();if(node.val>=low&&node.val<=high)sum+=node.val;if(node.left&&node.val>=low)stack.push(node.left);if(node.right&&node.val<=high)stack.push(node.right);}
  return sum;
}

Time: O(n) | Space: O(h) auxiliary space, excluding output

Saved in this browser only. Private to you.

JavaScript