import java.util.Random;

public class TreeDemo {

public static void main(String[] args){

//Library of words to be added to the tree.

String[] words = {"Amok", "Nirvana", "Levin", "Minotaur", "Naif",

"Brevet", "Dehort", "Costive", "Boffin", "Hoyle",

"Scion", "Pissoir", "Looby", "Kvell", "Redact", "Pi" };

//For easier readability, swap words for numbers.

String[] numbers = {"1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16"};

Random rand = new Random(); // Initialize Random

BinarySearchTree myTree = new BinarySearchTree(); // Initialize the Tree (make sure your tree class is named BinarySearchTree)

for (int addLoop = 0; addLoop

int r = rand.nextInt(16);

System.out.println("Adding: " + words[r]);

myTree.insert(words[r]); // Method call to the tree to insert nodes

}

System.out.println("---Searches---"); // Start multiple searches

myTree.search(words[rand.nextInt(16)]);

myTree.search(words[rand.nextInt(16)]);

myTree.search(words[rand.nextInt(16)]);

System.out.println("---Printing---"); // Print the tree using all

myTree.printPreOrder(); // three type of order

myTree.printInOrder();

myTree.printPostOrder();

}

}

Program Assignment #3 Write a program allows the user to enter and search for strings. When strings are added to the tree, they should be wrapped inside a node object that holds the string, the frequency (number of times) with which that string has been added to the tree, and references to two other nodes (children). The strings must be stored in a Binary Search Tree. You will need to implement your own Binary Search Tree (you may use the one we covered in class as a starting point). A driver has been provided for you (TreeDemo.java). You must use that class as your driver, without alterations. Be sure to analyze the driver code (specifically the methods and manner in which the methods are called) to be sure that your program functions properly In addition to the provided Tres, your project will also need two other classes: 1. BinarSechTe- This will serve as your container class. It needs to have functionality for adding nodes and searching (traversing) the tree Node - Your Binary Search Tree will be made up of Node objects. Each node object must reference two children and also contain the string entered by the user and the frequency of that string. 2. To submit your program, either zip all files together, or copy and paste all three into a single file and upload it to Canvas. The rubric below will be used in the grading of your program. Partial points may be awarded for each category. Category Program is free of errors and is well-commented Node class contains references to two children, the string, and the frequency of that word Successfully implement and instantiate a Binary Search Tree that holds Node objects Value New strings are successfully added to the tree in their correct position using alphabetical sorting. (If the word "Ball" is at the root, the word "Apple" would go left, but the word "Orange would go right) Strings already in the tree should not be added again; instead, the frequency should be increased Program correctly searches for and displays a node Program correctly uses Pre Order traversal to print all the nodes in the tree Program correctly uses In Order traversal to print all the nodes in the tree Program correctly uses Post Order traversal to print all the nodes in the tree 15 15 15 15 /100