BST Range Sum

Problem

Sum all values of a binary search tree that lie within [lo, hi] inclusive.

Insert values in order (duplicates ignored). Traverse the tree adding values in range, and prune the left subtree when the current value is at most lo and the right subtree when it is at least hi.

Return the range sum (0 for an empty tree).

Hint

Only descend left when the node exceeds lo and right when it is below hi.

Test cases

case 1

in: [[10,5,15,3,7,18],7,15]

expected: 32

case 2

in: [[1],1,1]

expected: 1

case 3

in: [[],1,5]

expected: 0

case 4

in: [[5,3,8],4,9]

expected: 13

Starter codePython

def bst_range_sum(values, lo, hi):
    # Your code here
    pass

4 test cases · run your code against them in the editor