Range Sum of BST Easy 0 attempts
LeetCode ↗

Range Sum of BST

Easy TreeBinary TreeDFS LeetCode

Given a BST, return the sum of values of all nodes with values between low and high inclusive.

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

Sample Input
—
Sample Output
—
Constraints
  • 1 <= number of nodes <= 2 * 10^4
  • 1 <= Node.val <= 10^5
  • 1 <= low <= high <= 10^5
Topics
TreeBinary TreeDFS

Pruned DFS

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);
}

Time: O(n) | Space: O(h)

Saved in this browser only. Private to you.

JavaScript