LeetCode 938: Range Sum of BST

Problem Restatement

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

low
high

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

[low, high]

Inclusive means both endpoints count.

So a node value should be included if:

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

Function shape:

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

Examples

Example 1:

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

The values inside [7, 15] are:

7, 10, 15

Their sum is:

7 + 10 + 15 = 32

So the answer is:

32

Example 2:

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

The values inside [6, 10] are:

6, 7, 10

Their sum is:

6 + 7 + 10 = 23

So the answer is:

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:

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:

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

Walkthrough

Use:

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:

10, 7, 15

The sum is:

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.

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

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

Implementation

# 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:

if root is None:
    return 0

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

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:

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

Otherwise, the current value is inside the range:

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

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()