Range Sum BST

Given a binary search tree, sum all node values within an inclusive range.

bst tree recursion

Given the root of a Binary Search Tree (BST) where each node has an integer value and left/right children (or None), write a function `range_sum_bst(root, low, high)` that returns the sum of all node values that are in the inclusive range [low, high]. The node class is defined as:

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
```

The input `root` may be `None` (empty tree), in which case the function should return 0.

Implement the function. You may write helper functions if needed. The BST property allows you to prune subtrees for efficiency, but a full traversal also works.

Constraints

The number of nodes in the tree is in the range [0, 10^4].
Node values are integers and are unique.
-10^5 <= Node.val <= 10^5
-10^5 <= low <= high <= 10^5
Time: O(N) worst case, O(log N) if balanced and range is narrow. Space: O(H) recursion depth.

Example

>>> # tree: [10,5,15,3,7,None,18]
>>> # range [7,15] -> sum = 10 + 15 + 7 = 32
>>> root = TreeNode(10, TreeNode(5, TreeNode(3), TreeNode(7)), TreeNode(15, None, TreeNode(18)))
>>> range_sum_bst(root, 7, 15)
32
>>> # empty tree
>>> range_sum_bst(None, 1, 10)
0

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use recursion: if the current node's value is below low, only the right subtree can have valid nodes. If above high, only the left subtree matters.

When the node value is inside the range, add it and recurse into both children.

Base case: if root is None, return 0.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.