Meta: Sum the Values of a Binary Search Tree That Fall Within an Inclusive Range

Sum the Values of a Binary Search Tree That Fall Within an Inclusive Range

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given a binary search tree with distinct node values and two integers `low` and `high`, return the sum of every node value `v` with `low <= v <= high`. Return `0` if no value falls in the range. In a binary search tree, for every node, all values in its left subtree are smaller than the node's value and all values in its right subtree are larger. ### Function Signature ```python def range_sum_bst(tree: list[int | None], low: int, high: int) -> int: ``` ### Rules - **Input format.** `tree` is the level-order serialization of the tree. `tree[0]` is the root; after it, entries are consumed two at a time as the left child and then the right child of each non-null node, in the order those nodes appear. `None` marks a missing child, children of missing nodes are not listed, and trailing `None` entries may be omitted. - The input is guaranteed to be a valid binary search tree. - Both bounds are inclusive. ### Constraints - `1 <= number of nodes <= 20000` - `1 <= node value <= 100000`, and all values are distinct. - `1 <= low <= high <= 100000` - The result fits in a signed 32-bit integer. ### Examples **Example 1** Input: `tree = [10, 5, 15, 3, 7, None, 18]`, `low = 7`, `high = 15` Output: `32` Explanation: the values in range are 7, 10, and 15. **Example 2** Input: `tree = [10, 5, 15, 3, 7, 13, 18, 1, None, 6]`, `low = 6`, `high = 10` Output: `23` Explanation: the values in range are 6, 7, and 10. **Example 3** Input: `tree = [10, 5, 15]`, `low = 11`, `high = 14` Output: `0` Explanation: no value lies between 11 and 14.

Overview: Given a binary search tree with distinct values in level-order form, return the sum of all node values that fall within an inclusive lower and upper bound, or zero when none do. It tests binary search tree traversal on trees of up to 20,000 nodes.

Given a binary search tree whose node values are distinct, and two integers `low` and `high`, return the sum of every node value `v` with `low <= v <= high`. Return `0` if no value falls in the range. In a binary search tree, for every node, all values in its left subtree are smaller than the node's value and all values in its right subtree are larger. Implement `range_sum_bst(tree, low, high)`. **Input format** - `tree` is the level-order serialization of the tree. `tree[0]` is the root; after it, entries are consumed two at a time as the left child and then the right child of each non-null node, in the order those nodes appear. - `None` marks a missing child (`null` in JavaScript and Java, an empty `std::optional<int>` in C++). Children of missing nodes are not listed, and trailing `None` entries may be omitted. - The input is guaranteed to be a valid binary search tree. - Both bounds are inclusive. **Output** Return the sum as a single integer. The result fits in a signed 32-bit integer (it never exceeds 2^31 - 1), so `int` is sufficient in Java and C++. **Example 1** Input: `tree = [10, 5, 15, 3, 7, None, 18]`, `low = 7`, `high = 15` Output: `32` Explanation: the values in range are 7, 10, and 15. **Example 2** Input: `tree = [10, 5, 15, 3, 7, 13, 18, 1, None, 6]`, `low = 6`, `high = 10` Output: `23` Explanation: the values in range are 6, 7, and 10. **Constraints** - `1 <= number of nodes <= 20000` - `1 <= node value <= 100000`, and all values are distinct. - `1 <= low <= high <= 100000` - The result fits in a signed 32-bit integer.

Constraints

1 <= number of nodes <= 20000
1 <= node value <= 100000, and all values are distinct
1 <= low <= high <= 100000
The result fits in a signed 32-bit integer
tree is a valid level-order serialization of a binary search tree; both bounds are inclusive

Examples

Input: ([10, 5, 15, 3, 7, None, 18], 7, 15)

Expected Output: 32

Explanation: Example 1: the values in range are 7, 10 and 15.

Input: ([10, 5, 15, 3, 7, 13, 18, 1, None, 6], 6, 10)

Expected Output: 23

Explanation: Example 2: 6, 7 and 10; 7 and 6 sit under node 5, which is below low.

Hints

Both bounds are inclusive: a node whose value equals low or high counts toward the sum.
When rebuilding the tree, remember that children are listed only for non-null nodes, so an entry's children are not simply at positions 2*i+1 and 2*i+2.
A valid tree can be a single chain of up to 20000 nodes, so make sure your approach copes with that depth.

Approach

Rebuild the tree from its level-order serialization, then walk it with BST pruning.

Parsing: the non-null entries appear in the same breadth-first order in which their children are listed. Give each non-null entry the next node index and keep a pointer head to the node whose children are being read. Each step consumes up to two entries (left, then right), skips None, and stops when the list runs out, which also handles omitted trailing None entries. Positions are not heap-style (2i+1, 2i+2), because children of missing nodes are not listed.

Traversal: use an explicit stack that starts at the root. Add a node's value when low <= v <= high. Push the left child only when v > low: every value in the left subtree is smaller than v, so if v <= low none of them can reach low. Push the right child only when v < high, by the symmetric argument.

Invariant and correctness: every node that is never visited lies outside [low, high], and every visited node is counted exactly once, so the total equals the required sum. A node outside the range can still have in-range descendants (in Example 2, 5 < 6 but its right subtree holds 7 and 6), so the traversal prunes only one side, never the whole subtree.

Edge cases: a single node, low == high, a range containing no node value (returns 0), and skewed chains up to 20000 nodes deep, which the explicit stack handles without recursion limits. All values are positive, so every partial sum is at most the final sum, which fits in a signed 32-bit integer.

Time complexity:

O(n)

Space complexity: