Range Sum of BST

LeetCode #938 [Easy]

Problem Statement

Calculate the sum of all node values in BST within a given range [L, R].

Example: Input: root=[10,5,15,3,7,null,18], L=7, R=15 → Output: 32

Approach: Recursive DFS

Explanation: Traverse tree, accumulate values within range.

Time Complexity: O(n)

Space Complexity: O(h)

function rangeSum(node, L, R):
    if node == NULL: return 0
    sum = 0
    if L <= node.val <= R:
        sum += node.val
    if node.val > L:
        sum += rangeSum(node.left, L, R)
    if node.val < R:
        sum += rangeSum(node.right, L, R)
    return sum
Heap Sort Flowchart

💡 Think: Skip subtrees outside [L,R]; add node if within range, recurse only where it can still fit.

Solve on LeetCode