We are given a BST and a range (startValue, endValue), we have to compute the sum of the nodes of the BST which fall in this range.
There is one additional requirement though. We have to optimise for millions of queries being performed on a given tree.
15 10 20 8 12 16 range = [10, 16] ans = 10 + 12 + 15 + 16 = 63
A naive solution can be to just traverse the array and keep summing the elements.
But we are required to optimise the solution for millions of read.
Whenever we hear terms like disproportionately more reads than writes, we should consider some pre-processing or caching to speed up the reads.
Here also we can pre-compute some values for the given tree to speed to up the queries.
With every node we are going to store 2 values:
1. Range of the values in the tree planted at that node.
2. Sum of the values in the tree planted at that node.
1. If a node has a range that's completely within the required range, return the sum stored with the node.
2. If not search recursively in the right and left substree to get the valid nodes sum.
3. Add the node's value if it falls in the range.