Show problems as
Classic problem #938EasyTreeDepth-First SearchBinary Search TreeBinary Tree

Range Sum of BST

Real-world version: Auditing a Fare Band in the Register
Tracked in this browser only
Read Range Sum of BST on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A tramway fare machine files the day's takings in a sorted register. Each entry in the register records one fare in pence and hangs two branches beneath it, a lighter branch and a heavier branch. Every fare filed anywhere in an entry's lighter branch is strictly smaller than that entry's own fare, and every fare filed anywhere in its heavier branch is strictly larger. No two entries record the same fare.

The register reaches you as register, which lists the entries one level at a time from the top down and, inside a level, from left to right with the lighter branch before the heavier one. Slot 0 holds the top entry. Reading the listing from the front, each entry takes the next two slots that nothing has taken yet: the first belongs to its lighter branch and the second to its heavier branch. A slot holding null means that branch is empty, and an empty branch takes no slots of its own. null slots at the very end of the listing may be left out.

An auditor is reconciling one fare band. Return the total of every fare in the register that is at least low and at most high, counting both ends of the band. If no fare falls in the band, the total is 0.

Examples

Example 1

Input
register = [32, 15, 47, 8, 23, 39, 55], low = 20, high = 45
Output
94

The register holds the fares 32, 15, 47, 8, 23, 39 and 55. Of those, 23, 32 and 39 are at least 20 and at most 45, and they come to 94.

Example 2

Input
register = [32, 15, 47, 8, 23, 39, 55], low = 47, high = 100
Output
102

Two fares, 47 and 55, are at least 47 and at most 100, so the audit line comes to 102.

Example 3

Input
register = [42], low = 1, high = 41
Output
0

The register holds one fare of 42, which is above the top of the band, so nothing is counted.

Example 4

Input
register = [70, 30, 90, 20, 50, 85, null, null, null, 45], low = 45, high = 85
Output
250

The fares 45, 50, 70 and 85 all lie inside the band, and together they come to 250.

Constraints

  • The number of entries in the register is in the range [1, 2 * 10^4].
  • 1 <= fare of an entry <= 10^5
  • 1 <= low <= high <= 10^5
  • All fares in the register are distinct.
  • register[0] holds an entry.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def band_total(register: list[int | None], low: int, high: int) -> int:
Java
public int bandTotal(Integer[] register, int low, int high)

More on the same topics