Practice/Meta/Leetcode 938. Range Sum of BST

Leetcode 938. Range Sum of BST

CodingMust

Problem

You are given the root node of a binary search tree (BST) along with two integers representing an inclusive range: low and high. Your task is to calculate and return the sum of all node values in the BST that fall within this range (inclusive of both boundaries).

Take advantage of the BST property where all values in the left subtree are smaller than the current node, and all values in the right subtree are larger. This allows you to avoid exploring entire subtrees when they cannot possibly contain values within the target range.

Requirements

1. Traverse only the necessary portions of the BST to find values within the range
2. Return the sum of all node values where low <= node.val <= high
3. Handle edge cases such as empty trees, single-node trees, and ranges that exclude all nodes
4. Optimize the solution by pruning subtrees that fall entirely outside the range

Constraints

• The number of nodes in the tree is in the range [1, 20000]
• 1 ≤= Node.val ≤= 10^5
• 1 ≤= low ≤= high ≤= 10^5
• All node values in the BST are unique
• Time complexity should be better than O(n) in most cases by pruning branches
• Space complexity should be O(h) where h is the height of the tree (due to recursion stack)

Examples

Example 1:

` Input: root = [10, 5, 15, 3, 7, null, 18], low = 7, high = 15 Output: 32 Explanation: The tree structure is: 10 /
5 15 / \
3 7 18

Nodes within range [7, 15]: 7, 10, 15 Sum: 7 + 10 + 15 = 32 `

Example 2:

Input: root = [10, 5, 15, 3, 7, 13, 18], low = 1, high = 20 Output: 71 Explanation: All nodes fall within the range, so we sum all values: 10 + 5 + 15 + 3 + 7 + 13 + 18 = 71

Example 3:

Input: root = [10, 5, 15, 3, 7, null, 18], low = 3, high = 7 Output: 15 Explanation: Nodes within range [3, 7]: 3, 5, 7 Sum: 3 + 5 + 7 = 15