Frontend School

Range Sum of Transaction IDs in BST

DSA
easy

Range Sum of Transaction IDs in BST

Easy
Tree
Binary Search Tree
Traversal

Overview

At Stripe, efficiently managing and querying transaction data is paramount. Transaction IDs are often numerical and can be structured in a way that allows for quick lookups and aggregations. This problem asks you to leverage the properties of a Binary Search Tree (BST) to quickly sum up transaction IDs that fall within a specified range, mimicking a common reporting or auditing requirement.

What you need to do / Task

Given the root of a Binary Search Tree (BST) where each node's val represents a unique transaction ID, and two integers, lowId and highId, your task is to return the sum of all transaction IDs in the BST that are within the inclusive range [lowId, highId].

Input & output

Input:

  • root: The root node of a Binary Search Tree. Each node has a val (number), left (TreeNode | null), and right (TreeNode | null).
  • lowId: An integer representing the lower bound of the inclusive range.
  • highId: An integer representing the upper bound of the inclusive range.

Output:

  • A single integer, representing the sum of all transaction IDs in the BST whose values are greater than or equal to lowId and less than or equal to highId.

Clarifications

  • The input tree is guaranteed to be a valid Binary Search Tree.
  • lowId will always be less than or equal to highId.
  • The transaction IDs in the tree are unique.
  • If the tree is empty or no transaction IDs fall within the specified range, the sum should be 0.

Examples

1

Example 1

Input:

root = [10,5,15,3,7,null,18], lowId = 7, highId = 15

Output:

32

Note:

The transaction IDs in the tree are [3, 5, 7, 10, 15, 18]. IDs within the range [7, 15] are 7, 10, 15. Their sum is 7 + 10 + 15 = 32.

2

Example 2

Input:

root = [10,5,15,3,7,13,18,1,null,6], lowId = 6, highId = 10

Output:

23

Note:

The transaction IDs are [1, 3, 5, 6, 7, 10, 13, 15, 18]. IDs within the range [6, 10] are 6, 7, 10. Their sum is 6 + 7 + 10 = 23.

3

Example 3

Input:

root = [10,5,15,3,7,null,18], lowId = 20, highId = 25

Output:

0

Note:

No transaction IDs in the tree are within the range [20, 25].

Constraints

Constraints & assumptions

  • The number of nodes in the tree will be between 0 and 10^4.
  • Each node's val (transaction ID) will be between 0 and 10^5.
  • lowId and highId will be between 0 and 10^5.
  • The sum of transaction IDs will fit within a 32-bit integer.

Out of scope

  • You do not need to validate if the input tree is a BST; assume it is valid.
  • You do not need to handle non-numeric transaction IDs or complex data types.

What interviewers evaluate

  • Correctness of the BST traversal logic to identify relevant nodes.
  • Efficiency of the solution, specifically how BST properties are leveraged to prune unnecessary searches.
  • Clarity and structure of the code, including appropriate variable naming.
  • Handling of edge cases such as empty trees or ranges outside the tree's values.

Loading editor...