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 balanced Binary Tree (not a Binary Search Tree). You will need to implement your own Binary 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 TreeDemo class, your project will also need two other classes: BinaryTree This will serve as your container class. It needs to have functionality for adding nodes and searching (traversing) the tree. Node Your Binary 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.

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 < 30; addLoop++){ // Loop to add items to the Tree 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(); } }