Range Sum of BST

Q: What is the time complexity of Range Sum of BST?

The pruned traversal visits the k nodes in range plus the nodes on at most two paths from the root: O(h + k) time for a tree of depth h , and O(n) when every value is in range. The stack or the recursion takes O(h) space.

Q: Can Range Sum of BST be solved with an in-order traversal?

Yes. An in-order traversal lists the values in increasing order, so you add values once they reach low and stop at the first one above high . The early stop saves work on the right side of the tree; pruning saves it on both sides.

Q: Should you use recursion or a stack for Range Sum of BST?

Both work. Here the depth is at most 14, so recursion stays shallow. An explicit stack avoids the recursion limit on a tall tree with thousands of levels.

EasyBinary search tree Tree traversal

+10

A binary search tree is stored in the array tree in level order: the root is at index 0, the children of the node at index i are at 2*i+1 (left) and 2*i+2 (right), and -1 marks an empty spot. In a binary search tree, every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger.

Return the sum of all node values v with low ≤ v ≤ high, or 0 when there are none.

Function

rangeSumBST(tree: integer-array, low: integer, high: integer) → integer

treeinteger-array: the binary search tree in level order, with -1 for an empty spot
lowinteger: the smallest value to count
highinteger: the largest value to count
Returnsinteger: the sum of the node values between low and high, both included

Constraints

1 ≤ tree.length ≤ 32767
Each tree[i] is -1 or a value with 0 ≤ tree[i] ≤ 10⁵.
tree[0] is never -1, so the tree has at least one node.
The array may end with extra -1 entries past the last node.
Both children of an empty spot are empty too, and the depth is at most 14.
The tree is a valid binary search tree, so all its values are distinct.
0 ≤ low ≤ high ≤ 10⁵
The answer fits in a 32-bit signed integer.

Examples

Input: tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]low = 9high = 31
Output: 88
Explanation: The values from 9 to 31 are 10, 12, 15, 20 and 31, which add up to 88. The 3, 8 and 40 fall outside the range.

Input: tree = [50, 25, 75, -1, -1, -1, -1]low = 60high = 70
Output: 0
Explanation: The tree holds 25, 50 and 75, and none of them lies between 60 and 70, so the sum is 0. The four -1 entries are the empty child spots of 25 and 75.

Input: tree = [6, 2, 9, 1, 4, 7]low = 4high = 4
Output: 4
Explanation: With low and high both 4, only a node of value 4 counts. The 4 at index 4 is the right child of 2, so the answer is 4.

Follow-up

If you had to answer thousands of different (low, high) queries on the same tree, how could you answer each one in O(log n) time?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Visiting every node and adding the values in range is correct. The search tree order lets you do less: a node's value tells you which side holds the smaller and the larger values, so a subtree that cannot reach the range is never opened.

Visit every node

Intuition

A child is real only if its index is inside the array and the value there is not -1. In the first example, the 12 at index 4 has 10 and 15 at indexes 9 and 10, and the 31 at index 2 has an empty left spot at index 5.

Every value in the range sits in some node, so a stack traversal that reaches every node and adds the values with low ≤ v ≤ high gets the right sum. It ignores the search tree order, so it touches all n nodes even when the range holds only a few values.

Algorithm

Push the root index 0 on a stack and set total = 0.
Pop an index i. If low ≤ tree[i] ≤ high, add tree[i] to total.
Push 2*i+1 and 2*i+2 when they are inside the array and not -1.
When the stack is empty, return total.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and tree[left] != -1:
            stack.append(left)
        if right < n and tree[right] != -1:
            stack.append(right)
    return total

Prune with the search tree order

Intuition

The left subtree of a node holding v has only values smaller than v. If v ≤ low, none of them is in range, so skip that subtree. If v ≥ high, the right subtree has only values above high, so skip it. In the first example the 31 equals high, so its right child 40 is never pushed. The 8 is below low, so its left child 3 is skipped, but its right child 12 is visited, because values between 8 and 20 can be in range.

You visit the k values in the range plus the nodes on at most two paths from the root: O(h + k) time for depth h. When the range covers the whole tree that is still O(n).

Algorithm

Push the root index 0 on a stack and set total = 0.
Pop an index i and read v = tree[i]. If low ≤ v ≤ high, add v to total.
If v > low, push the left child 2*i+1 when it is real.
If v < high, push the right child 2*i+2 when it is real.
When the stack is empty, return total.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        # Smaller values sit on the left, larger on the right: skip a side the range cannot reach.
        if value > low and left < n and tree[left] != -1:
            stack.append(left)
        if value < high and right < n and tree[right] != -1:
            stack.append(right)
    return total

Pitfalls and edge cases

Using strict comparisons. Both ends count, so the third example, with low = high = 4, must count the 4.
Pruning one step too early. At v = low the left subtree can go, but at v = low + 1 it may hold low itself.
Dropping both sides of a node outside the range. The 8 in the first example is below low, yet its right subtree holds 10, 12 and 15.
Reading a child past the end of the array. Check 2*i+1 < tree.length before reading, and treat -1 as no child.
In Lua and R, arrays start at 1: keep node indexes 0-based for the 2*i+1 arithmetic and read tree[i + 1].

Frequently asked questions3

What is the time complexity of Range Sum of BST?

The pruned traversal visits the k nodes in range plus the nodes on at most two paths from the root: O(h + k) time for a tree of depth h, and O(n) when every value is in range. The stack or the recursion takes O(h) space.

Can Range Sum of BST be solved with an in-order traversal?

Yes. An in-order traversal lists the values in increasing order, so you add values once they reach low and stop at the first one above high. The early stop saves work on the right side of the tree; pruning saves it on both sides.

Should you use recursion or a stack for Range Sum of BST?

Both work. Here the depth is at most 14, so recursion stays shallow. An explicit stack avoids the recursion limit on a tall tree with thousands of levels.

def rangeSumBST(tree, low, high):
    # Write code here

Test #1

Test #2

Test #3

Arguments

tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]
low = 9
high = 31

Expected Output