Range Sum of BST

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

A traversal that prunes with the search tree order visits the k nodes in the range plus the nodes on at most two paths from the root, O(h + k) time for a tree of depth h . In the worst case, when every value is in range, that is O(n) . The extra space is O(h) for the stack or the recursion.

Q: Why can you skip subtrees in Range Sum of BST?

In a binary search tree every value on the left of a node is smaller than it and every value on the right is larger. If the node's value is at most low , nothing on its left can reach the range, and if it is at least high , nothing on its right can. Skipping those sides never misses a value in range.

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

Yes. An in-order traversal of a binary search tree lists the values in increasing order, so you can add values once they reach low and stop as soon as one passes high . It gives the same answer, and the early stop saves work on the right side of the tree, while the pruned search also saves work on the left.

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

Both work. Recursion is shorter, and here the depth is at most 14, so the call stack stays small. An explicit stack avoids the recursion limit entirely, which matters on a tall tree with thousands of levels, and it is what the solutions on this page use.

EasyBinary search tree Tree traversal

+10

You get a binary search tree stored in the array tree in level order, and two numbers low and high. The root sits at index 0, the children of the node at index i sit at 2*i+1 (left) and 2*i+2 (right), -1 marks an empty spot, and the array may end with extra -1 entries. 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.

Write a function named rangeSumBST that returns the sum of all node values v with low ≤ v ≤ high, or 0 when no value is in that range.

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.

+14 hidden tests on Submit

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

Adding up every value in the range is a plain traversal: visit each node and keep the ones that fit. The search tree order lets you do better. A node's value tells you on which side the smaller and larger values live, so whole subtrees can be skipped without looking at a single node inside them.

Visit every node

Intuition

First, how to move around the array. The node at index i has its left child at 2*i+1 and its right child at 2*i+2. A child is real only if its index is inside the array and the value there is not -1. In [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15], the root 20 has 8 and 31 at indexes 1 and 2, the 12 at index 4 has 10 and 15 at indexes 9 and 10, and the 31 has an empty left spot at index 5.

Now the idea. Every value in the range sits in some node, so a traversal that reaches every node and adds the values with low ≤ v ≤ high gets the right sum. Use a stack of node indexes. Start with the root, pop an index, add its value if it is in range, and push each real child.

This ignores the search tree property entirely; it works on any binary tree. It touches all n nodes, O(n) time, and the stack holds the pending children along one path, O(h) space for depth h. When the range covers a few values in a tree of thousands of nodes, most of that work is wasted.

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

Keep the same stack traversal, but use the order. Say a node holds v. Its left subtree holds only values smaller than v. If v ≤ low, every one of them is below low, so the left subtree cannot add anything: skip it. In the same way, if v ≥ high, the right subtree holds only values above high: skip it. So you push the left child only when v > low, and the right child only when v < high.

In the first example with range [9, 31], the 31 equals high, so its right child 40 is never pushed. The 8 is below low, so its left child 3 is skipped, while its right child 12 still gets visited, because values between 8 and 20 can be in range.

The nodes you visit are the k values in the range plus at most two root-to-leaf paths along its edges, so the time is O(h + k). When the range covers the whole tree this is still O(n), but a narrow range in a large tree touches only a few dozen nodes. The stack needs O(h) space.

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

Most wrong answers come from the boundaries of the range or of the array.

Using strict comparisons. Both ends are included, so a node equal to low or high counts.
Pruning one step too early. When v equals low, the left subtree can be skipped, but when v is low + 1 it cannot: it may hold low itself.
Stopping at a node outside the range. A node below low can still have a right subtree full of values in range, so skip only the side the order rules out.
Reading a child index past the end of the array. Check 2*i+1 < tree.length before reading the value, and treat -1 as no child.
Mixing up the offset in Lua and R, where arrays start at 1. Keep the node indexes 0-based for the 2*i+1 arithmetic and read tree[i + 1].

Frequently asked questions4

What is the time complexity of Range Sum of BST?

A traversal that prunes with the search tree order visits the k nodes in the range plus the nodes on at most two paths from the root, O(h + k) time for a tree of depth h. In the worst case, when every value is in range, that is O(n). The extra space is O(h) for the stack or the recursion.

Why can you skip subtrees in Range Sum of BST?

In a binary search tree every value on the left of a node is smaller than it and every value on the right is larger. If the node's value is at most low, nothing on its left can reach the range, and if it is at least high, nothing on its right can. Skipping those sides never misses a value in range.

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

Yes. An in-order traversal of a binary search tree lists the values in increasing order, so you can add values once they reach low and stop as soon as one passes high. It gives the same answer, and the early stop saves work on the right side of the tree, while the pruned search also saves work on the left.

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

Both work. Recursion is shorter, and here the depth is at most 14, so the call stack stays small. An explicit stack avoids the recursion limit entirely, which matters on a tall tree with thousands of levels, and it is what the solutions on this page use.

Python

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

Test cases

Case 1

Case 2

Case 3

Input

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

Expected