Frontend School

Range Sum of BST

DSA
easy

Range Sum of BST

Easy
Tree
Binary Search Tree
Depth-First Search
Recursion

Overview

In many applications, such as database indexing or financial data analysis, efficiently querying data within a specific range is crucial. Binary Search Trees (BSTs) are fundamental data structures that can support such range queries effectively. This problem assesses your ability to leverage the inherent properties of a BST to efficiently compute the sum of node values within a given numerical range.

What you need to do / Task

Your task is to implement a function rangeSumBST that takes the root of a Binary Search Tree (BST) and two integers, low and high, as input. The function should return the sum of all node values (Node.val) such that low <= Node.val <= high.

To achieve optimal performance, your solution should make effective use of the BST properties to avoid unnecessary traversals of subtrees that cannot possibly contain values within the specified range.

Input & output

Function Signature:

function rangeSumBST(root: TreeNode | null, low: number, high: number): number;

Input:

  • root: A TreeNode representing the root of a Binary Search Tree. If the tree is empty, root will be null.
  • low: An integer representing the inclusive lower bound of the desired range.
  • high: An integer representing the inclusive upper bound of the desired range.

Output:

  • A single integer representing the sum of all node values in the BST that fall within the [low, high] range (inclusive).

Clarifications

  • If the root is null (an empty tree), the sum should be 0.
  • The range [low, high] is always valid, meaning low <= high.
  • All Node.val are unique integers.

Examples

1

Example 1

Input:

root = [10,5,15,3,7,null,18], low = 7, high = 15

Output:

32

Note:

Nodes with values 7, 10, and 15 are within the range [7, 15]. Their sum is 7 + 10 + 15 = 32.

2

Example 2

Input:

root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10

Output:

23

Note:

Nodes with values 6, 7, and 10 are within the range [6, 10]. Their sum is 6 + 7 + 10 = 23.

3

Example 3

Input:

root = [1,2,3], low = 10, high = 20

Output:

0

Note:

No nodes in the tree have values within the range [10, 20].

Constraints

Constraints & assumptions

  • The number of nodes in the tree is in the range [0, 10^4].
  • Each Node.val is an integer in the range [0, 10^5].
  • low and high are integers in the range [0, 10^5].
  • low <= high.
  • The tree is guaranteed to be a valid Binary Search Tree (BST).

Out of scope

  • Error handling for invalid inputs (e.g., root not being a valid BST, low > high).
  • Modifying the tree structure.

What interviewers evaluate

  • Correctness: Does the algorithm accurately sum all values within the range?
  • Efficiency: Does the solution leverage BST properties to avoid unnecessary computations, achieving optimal time complexity?
  • Edge Cases: Is the solution robust enough to handle an empty tree or ranges outside the tree's value distribution?
  • Code Quality: Is the code clear, well-structured, and easy to understand?

Loading editor...