# LeetCode 938: Range Sum of BST

## Problem Restatement

We are given the root of a binary search tree and two integers:

```python
low
high
```

We need to return the sum of all node values that are inside the inclusive range:

```text
[low, high]
```

Inclusive means both endpoints count.

So a node value should be included if:

```python
low <= node.val <= high
```

The official statement asks for the sum of values of all nodes in a BST whose values lie in the inclusive range `[low, high]`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Root node of a binary search tree |
| Input | Integers `low` and `high` |
| Output | Sum of node values in `[low, high]` |
| Tree property | Left subtree values are smaller, right subtree values are larger |
| Range | Inclusive |

Function shape:

```python
class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        ...
```

## Examples

Example 1:

```python
root = [10, 5, 15, 3, 7, None, 18]
low = 7
high = 15
```

The values inside `[7, 15]` are:

```text
7, 10, 15
```

Their sum is:

```text
7 + 10 + 15 = 32
```

So the answer is:

```python
32
```

Example 2:

```python
root = [10, 5, 15, 3, 7, 13, 18, 1, None, 6]
low = 6
high = 10
```

The values inside `[6, 10]` are:

```text
6, 7, 10
```

Their sum is:

```text
6 + 7 + 10 = 23
```

So the answer is:

```python
23
```

These examples match the standard problem examples.

## First Thought: Traverse Every Node

A direct solution is to visit every node in the tree.

For each node:

1. Check whether its value is in `[low, high]`.
2. If yes, add it to the answer.
3. Continue to both children.

This works for any binary tree.

But the input is a binary search tree, so we can do better in practice by skipping branches that cannot contain useful values.

## Key Insight

A binary search tree has ordered subtrees.

For a node with value `x`:

| Condition | What we know |
|---|---|
| `x < low` | The node is too small, and the whole left subtree is also too small |
| `x > high` | The node is too large, and the whole right subtree is also too large |
| `low <= x <= high` | The node should be added, and both sides may contain valid values |

So we prune the search.

If `root.val < low`, we only search the right subtree.

If `root.val > high`, we only search the left subtree.

Otherwise, we add `root.val` and search both children.

## Algorithm

Use DFS.

At each node:

1. If the node is `None`, return `0`.
2. If `node.val < low`, return the result from the right subtree.
3. If `node.val > high`, return the result from the left subtree.
4. Otherwise, return:

```python
node.val + dfs(node.left) + dfs(node.right)
```

## Walkthrough

Use:

```python
root = [10, 5, 15, 3, 7, None, 18]
low = 7
high = 15
```

Start at `10`.

`10` is inside `[7, 15]`, so include it.

Search both sides.

Left child is `5`.

`5 < 7`, so `5` and its left subtree are too small. We skip left and only search right.

Right child of `5` is `7`.

`7` is inside range, so include it.

Right child of root is `15`.

`15` is inside range, so include it.

Right child of `15` is `18`.

`18 > 15`, so skip its right subtree.

The included values are:

```text
10, 7, 15
```

The sum is:

```python
32
```

## Correctness

The algorithm only skips a subtree when the BST ordering proves that every value in that subtree is outside the range.

If `node.val < low`, then every value in the left subtree is smaller than `node.val`, so every value in the left subtree is also smaller than `low`. None of those nodes can contribute to the answer, so skipping the left subtree is correct.

If `node.val > high`, then every value in the right subtree is larger than `node.val`, so every value in the right subtree is also larger than `high`. None of those nodes can contribute to the answer, so skipping the right subtree is correct.

If `node.val` lies in `[low, high]`, the algorithm adds it. Both subtrees may still contain valid values, so the algorithm searches both sides.

By applying this reasoning at every node, the algorithm includes every valid node value and excludes every invalid node value.

Therefore, the returned sum is exactly the sum of all node values in the inclusive range.

## Complexity

Let `n` be the number of nodes and `h` be the height of the tree.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` worst case | In the worst case, many nodes may need to be visited |
| Space | `O(h)` | Recursion stack height |

For a balanced tree, `h = O(log n)`.

For a skewed tree, `h = O(n)`.

## Implementation

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if root is None:
            return 0

        if root.val < low:
            return self.rangeSumBST(root.right, low, high)

        if root.val > high:
            return self.rangeSumBST(root.left, low, high)

        return (
            root.val
            + self.rangeSumBST(root.left, low, high)
            + self.rangeSumBST(root.right, low, high)
        )
```

## Code Explanation

The base case handles an empty subtree:

```python
if root is None:
    return 0
```

If the current value is too small, the left subtree is also too small:

```python
if root.val < low:
    return self.rangeSumBST(root.right, low, high)
```

If the current value is too large, the right subtree is also too large:

```python
if root.val > high:
    return self.rangeSumBST(root.left, low, high)
```

Otherwise, the current value is inside the range:

```python
return (
    root.val
    + self.rangeSumBST(root.left, low, high)
    + self.rangeSumBST(root.right, low, high)
)
```

So we add it and continue searching both subtrees.

## Testing

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

def run_tests():
    s = Solution()

    root = TreeNode(
        10,
        TreeNode(5, TreeNode(3), TreeNode(7)),
        TreeNode(15, None, TreeNode(18)),
    )
    assert s.rangeSumBST(root, 7, 15) == 32

    root = TreeNode(
        10,
        TreeNode(5, TreeNode(3, TreeNode(1)), TreeNode(7, TreeNode(6))),
        TreeNode(15, TreeNode(13), TreeNode(18)),
    )
    assert s.rangeSumBST(root, 6, 10) == 23

    root = TreeNode(5)
    assert s.rangeSumBST(root, 5, 5) == 5
    assert s.rangeSumBST(root, 1, 4) == 0

    root = TreeNode(2, TreeNode(1), TreeNode(3))
    assert s.rangeSumBST(root, 1, 3) == 6

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Standard example 1 | Checks normal pruning and inclusion |
| Standard example 2 | Includes lower endpoint and middle values |
| Single node inside range | Minimum tree with match |
| Single node outside range | Minimum tree without match |
| Whole tree in range | Every node contributes |