FastPrep
Problem · Tree

Repeated BST Range Sum and Average

Learn this problem
● MediumMeta logoMetaFULLTIMEONSITE INTERVIEW
See Meta hiring insights

Problem statement

Given a binary search tree with unique integer keys and an ordered batch of inclusive range queries, preprocess the tree and answer every query.

For each query [low, high], return one row [sum, average]:

  • sum is the sum of all keys x satisfying low <= x <= high.
  • average is their arithmetic mean.
  • When the range contains no key, return [0.0, 0.0].

Return the rows in query order. Both values use double in the runner output.

Function

rangeAggregates(root: TreeNode, queries: int[][]) → double[][]

Examples

Example 1

root = [10,5,15,3,7,null,18]queries = [[7,15],[6,10],[16,17]]return = [[32.0,10.666666666666666],[17.0,8.5],[0.0,0.0]]

The first range contains 7, 10, and 15. The second contains 7 and 10. The third is empty.

Example 2

root = [4,2,6,1,3,5,7]queries = [[1,7],[4,4],[8,9]]return = [[28.0,4.0],[4.0,4.0],[0.0,0.0]]

The full range contains all seven keys, the single-point range contains only 4, and the last range contains none.

Example 3

root = []queries = [[-5,5]]return = [[0.0,0.0]]

An empty tree contributes no values to any range.

Constraints

  • The tree contains from 0 through 200000 nodes.
  • Every key is unique and lies between -10^9 and 10^9, inclusive.
  • The input satisfies the binary search tree ordering invariant.
  • 1 <= queries.length <= 200000.
  • Every query satisfies -10^9 <= low <= high <= 10^9.
  • Every range sum fits a signed 64-bit integer.

More Meta problems

drafts saved locally
public double[][] rangeAggregates(TreeNode root, int[][] queries) {
    // Write your code here.
}
root[10,5,15,3,7,null,18]
queries[[7,15],[6,10],[16,17]]
expected[[32.0,10.666666666666666],[17.0,8.5],[0.0,0.0]]
checking account