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

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

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.

Inclusive Range Sum in a Level-Order Binary Search Tree

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.

Hints

1. Both bounds are inclusive: a node whose value equals low or high counts toward the sum.
2. When rebuilding the tree, remember that children are listed only for non-null nodes, so an entry's children are not simply at positions 2i+1 and 2i+2.
3. 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: O(n)