A5 Due Monday by 11:59pm Points 50 A2-A6 Rubric Assignment #5 This assignment has you develop a new class hierarchy based on a Tree class. You will use it to create a binary tree that inserts new...

A5 Due Monday by 11:59pm Points 50 A2-A6 Rubric Assignment #5 This assignment has you develop a new class hierarchy based on a Tree class. You will use it to create a binary tree that inserts new nodes in order, balance the tree (Program 5A) and determine whether a second set of words are in the tree or not. For the second part (Program 5B), implement three traversals: in-order, pre-order, and post-order. As before, the input is a sequence of words; however, this assignment introduces a "sentinel" to indicate the end-of-the-tree. It has not been needed before this assignment but makes multiple test cases easier here. It works like this: every node is a whitespace delimited word (a label) except for the last word which is reserved as the sentinel. For this assignment, the sentinel is "EOF" (without the double-quotes). This means that no node can have the label EOF but we simply accept that to keep the focus on the algorithm/data structure and not the I/O. As usual, any output of any program that begins with a pound sign (#) will be ignored and, of course, the Coding Canon applies. Program 5A: Binary Search Tree Description For this program, you will need a container class - - something very very similar to Node in the previous assignments. In place of List, you will need a new class. The name Tree is appropriate. The responsibility of the first program is simply to create a binary tree with the property that (i) all of the nodes to the left are less than or equal (lexicographically) to the current node and (ii) all of the nodes to the right are greater than the current node. Use the basic linked list Node and List as an approximate guide and a new class hierarchy called Node and Tree that provides an infrastructure to implement binary trees. The internal Node should have an string payload and, of course, two subtree pointers. INPUT: the input is a sequence of whitespace separated nodes that are used to construct the tree. When the sentinel is reached, then the next set of whitespace-separated words are used to search the tree. For each input word, the output is the word in surrounded by double quotes and either "found" or "not found" (based on whether the word was in the tree or not, no quotes) and then the end-of-line character. For example, if the input is abc def ghi EOF jkl def EOF ^D Then output would be: "jkl" not found "def" found (More sample input/output may follow but you will need to make your own test cases as well.) Program 5B: Traversals Description Read in a list of words (with an EOF sentinel) and then output the entire resulting binary tree three times. First, with the a heading In-Order XXXXXXXXXXfollowed by a list of words (one per line) followed by a blank line. Next is the heading "Pre-Order" (with a horizontal line), the words, and a blank line. Last is the heading "Post-Order" with the words. The meaning of pre-order, post-order, and in-order are the common meaning for rooted trees. Total Points: 50 Criteria Ratings Pts 20 pts 30 pts Functional Correctness Each component will be evaluated for how many of the requirements are met. See the text for specific requirements. 20 to >0.0 pts Full Marks 0 pts No Marks Code Style and Formating Please write your code neatly. Use naming conventions, add comments, use correct indentation, and be organized. Your code should not be difficult to read and understand. 30 to >0.0 pts Full Marks 0 pts No Marks