Question

Write a Java 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.

Answer 1

Program:

import java.util.*;
import java.io.*;

//Node class
class Node
{
int key;
Node left, right;

public Node() {}

public Node(int num) {
key = num;
left = null;
right = null;
}
}

//BinarySearchTree class
class BinarySearchTree
{
   Node root;
   //constructor
   public BinarySearchTree()
   {
       root = null;
   }
   //Helper method: insert to the BinarySearchTree
   private Node insert(Node root, int data)
   {
       if(root==null){
           root = new Node(data);
           return root;
       }
       else if(root.key > data)
       {
           Node left = insert(root.left, data);
           root.left = left;
       }
       else
       {
           Node right = insert(root.right, data);
           root.right = right;
       }
  
       return root;
   }
   //insert to the BinarySearchTree
   public void insert(int data)
   {
       root = insert(root, data);
   }
   //Helper method: sum the numbers within the range [a, b]
   private int sumOfNumbers(Node root, int a, int b)
   {
       if(root==null)
           return 0;
       if(root.key>=a && root.key<=b)
           return root.key + sumOfNumbers(root.left, a, b) + sumOfNumbers(root.right, a, b);
       return sumOfNumbers(root.left, a, b) + sumOfNumbers(root.right, a, b);
   }
   //sum the numbers within the range [a, b]
   public int sumOfNumbers(int a, int b)
   {
       return sumOfNumbers(root, a, b);
   }

}

//RangeOfData class
class RangeOfData
{  
   //main method
   public static void main (String[] args) throws IOException
   {
       //open the file
       Scanner sc = new Scanner(new File("dataX.txt"));
      
       BinarySearchTree bst = new BinarySearchTree();
      
       //read data and insert to the BinarySearchTree
       while(sc.hasNextInt())
       {
           int data = sc.nextInt();
           bst.insert(data);
       }
      
       //open the file
       sc = new Scanner(new File("rangeX.txt"));
      
       //read the range and sum of the
       while(sc.hasNextInt())
       {
           int a = sc.nextInt();
           int b = sc.nextInt();
           //sum the numbers within the range [a, b]
           int sum = bst.sumOfNumbers(a, b);
           //display the sum
           System.out.println ("Range["+a +","+b+"]. Sum = " + sum);
       }
   }
}

dataX.txt

3 -2 2 5 2 -6 1

rangeX.txt

-3 4
0 5

Output:

Range[-3,4]. Sum = 6
Range[0,5]. Sum = 13

Note: Whether you face any problem or need any modification then share with me in the comment section, I'll happy to help you.