Compute BST range sum
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given the root of a binary search tree and two integers low and high (inclusive), compute the sum of values of all nodes with low <= val <= high. Provide both recursive and iterative solutions that prune branches using BST properties, and analyze time and space complexity.
Quick Answer: This question evaluates understanding of binary search tree properties, traversal techniques, and the ability to implement both recursive and iterative algorithms while reasoning about time and space complexity.
You are given a binary search tree (BST) encoded as a **level-order array** `tree`, where `tree[i]` is the value at position `i` and `None` marks a missing node. For any node at index `i`, its left child is at index `2*i + 1` and its right child is at index `2*i + 2`. You are also given two integers `low` and `high`.
Return the sum of the values of all nodes whose value lies in the inclusive range `[low, high]` (i.e. `low <= val <= high`).
Because the tree is a BST, you can prune entire subtrees: at a node with value `v`, if `v < low` you never need to descend left, and if `v > high` you never need to descend right.
**Example**
```
tree = [10, 5, 15, 3, 7, None, 18], low = 7, high = 15
```
The tree is:
```
10
/ \
5 15
/ \ \
3 7 18
```
Nodes in [7, 15] are 7, 10, 15 -> sum = 32.
Return `32`.
Constraints
- 0 <= number of nodes <= 2 * 10^4
- Each node value fits in a 32-bit signed integer
- All node values in the BST are distinct
- -10^9 <= low <= high <= 10^9
- The input array is a valid level-order encoding of a BST (None marks a missing child)
Examples
Input: ([10, 5, 15, 3, 7, None, 18], 7, 15)
Expected Output: 32
Explanation: Tree rooted at 10 with children 5 and 15; values in [7,15] are 7, 10, 15 -> 7+10+15 = 32.
Input: ([10, 5, 15, 3, 7, 13, 18, 1, None, 6], 6, 10)
Expected Output: 23
Explanation: Values in [6,10] are 6, 7, 10 -> 6+7+10 = 23. The subtrees rooted at 13/15/18 and at 3 (mostly) are pruned by BST bounds.
Hints
- Use the BST ordering to avoid visiting subtrees that cannot contain in-range values: at a node with value v, skip the left subtree when v <= low and skip the right subtree when v >= high.
- With the array encoding, the left child of index i is at 2*i+1 and the right child is at 2*i+2 — recurse on those indices instead of pointer children.
- Handle the empty tree (empty array or a None root) by returning 0 before any traversal.
- An iterative version can replace recursion with an explicit stack of indices, applying the same two pruning checks before pushing a child.