I have already implemented a binary search tree:

class BinarySearchTree { class Node { int key; Node left, right; public Node(int item) { key = item; left = right = null; } } Node root; BinarySearchTree() { root = null; } void insert(int key) { root = insertNode(root, key); } Node insertNode(Node root, int key) { if (root == null) { root = new Node(key); return root; } if (key  root.key) root.right = insertNode(root.right, key); return root; } void inorder() { inorderTree(root); } void inorderTree(Node root) { if (root != null) { inorderTree(root.left); System.out.println(root.key); inorderTree(root.right); } } public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); tree.insert(49); tree.insert(34); tree.insert(21); tree.insert(98); tree.insert(342); tree.insert(3); tree.insert(10); tree.inorder(); } }

Implement Search (T data) to search for a node having value of key - data in a Binary Search Tree. 4. Use the Binary Search Tree to build a search tree using the given input file that consists of two fields: a UPC key and the corresponding description. Use the search tree created to find the description associated with a given set of UPC keys. The input file UPC. csv provides the key and corresponding descriptions in a comma separated file and the various search keys are provided in the file input. dat. First test the program by entering couple of keys manually and print the description. Once you are convinced the program is working correctly, test the program for the given search keys and determine the total time taken to complete the search. 5