Write a program to read a set of integers from a file, dataX, and a set of ranges from a second file, rangeX, and, for each range [a, b] in rangeX, report the SUM of all the integers in dataX which are in the range [a, b]. As the integers are read from file dataX, insert them in a binary search tree. After all the integers have been inserted into the binary search tree, read the ranges from file rangeX and query the binary search tree to report the sum.

For instance, if file dataX has the integers (3, 2, 2, 5, 2, 6, 1) and file rangeX has the ranges ([3, 4], [0, 5]) then the output should be:

Range [-3,4]. Sum = 6.

Range [0,5]. Sum = 13.

1. Describe how to modify the binary search tree data structure to support computing the sum in a range in (h) time.

2. Describe the algorithm to insert elements in your modified binary search tree and GIVE PSEUDO-CODE for your insertion algorithm.

3. Describe the algorithm to report the sum of the elements in range [a, b] and GIVE PSEUDO-CODE for your reporting algorithm.

4. Implement your algorithm in Java, implementing the binary tree from scratch.

**Specificatiions**

-Name your program sumRange.

- Your program has two command line arguments, dataX and rangeX, representing an input data file name and an input range file name. A user runs your program on files dataX, rangeX, by typing: sumRange dataX rangeX

- Output from your program should be a list of ranges and the sum of the integers in each range. Each range and sum should be on a separate line in the output. 1

- File dataX consists of of integers, one per line. Read the file until reaching the end of file.

- File rangeX consists of pairs of integers, one pair per line. Read the file until reaching the end of file.

- Your program MUST insert the integers from dataX in a binary search tree in the order they are read from dataX.

- Your program should have a function/method Function Insert (or btreeInsert) for inserting an integer in the binary search tree. Insert (x) inserts integer x into the binary search tree. Insert (x) should run in (h) time where h is the height of the tree.

- Your program should have a function/method sumRange (or btreeSumRange) for computing the sum of all the elements in the btree which lie in the range. Function sumRange (a, b) returns the sum of all the elements x in the binary search tree where a x b. sumRange (a,b) should run in (h) time where h is the height of the tree.

- In Java, store the integer values in an integer of type long