Order Description

Develop a Java application to implement a binary tree data structure. A tree data structure starts from the top node, called the root. Each node in the tree has a set of children, which are also nodes of the tree and can have children of their own, and so on. This keeps on going till we get to the bottom of the tree, to the “leaf” nodes. Each node in the tree, except for the root, has a parent. A binary tree is a specialized form of a tree data structure in which each node in the tree has at most two children. Shown below is a labelled diagram of a binary tree.

A binary tree can be represented using the format in the example below. Each line contains at most three characters. The first character is the ID of the node itself. The next two characters are the child nodes. If a line has only 2 characters, then that node has only one child. If a line has one character only, then it is a leaf node

The application should exhibit the following functionality (see the sample output provided): • Display a menu to the user and request for the desired option. • Based on the user’s input, request for additional information as follows: o If the user wants to add a node, request for the name / ID of the new node to be added as well as the name of the desired parent of that node. ▪ If the parent node already has two children, the new node cannot be added since this is a binary tree (and each node can only have at most two children). • Display an appropriate message to the user. • Display the menu again for the user to make another choice. ▪ If the parent node already has one child, use recursion to add the new node as the second child (right child) of the parent node. • Display the new tree with the new node added. This should be done using a recursive method in your project (printTree() ). • Display the menu options. ▪ If the parent node has no children, use recursion to add the new node as the left child of the parent node. • Display the new tree with the new node added. • Display the menu options. o If the user wants to know the size of the tree (i.e., the number of nodes in the tree or sub-tree), request for the name / ID of the node that is the root of the desired tree / sub-tree. The size of a tree or sub-tree is the number of its children and other ‘descendants’ (including any leaf nodes) plus one – the root node itself. For example, the size of the sub-tree with root ‘B’ in Figure 2 above is 7. ▪ Recursively count the number of nodes in the tree / sub-tree and display this with an appropriate message. • Display the newly updated tree. • Display the menu options.

o If the user wants to find a node, request for the name / ID of the node to search for in the tree. ▪ Search recursively for the node in the tree; if the node is found, display an appropriate message, otherwise, indicate that the node does not exist in the tree. • Display the menu options. o If the user wants to exit, terminate the program. A sample output (to be followed exactly) is included below. Example Output A B C B D E D H I H I E J K J K C F G F L L G There are 12 nodes in this tree. Please select from one of the following options: 1. Add Node 2. Tree Size 3. Find Node 0. Exit ->1 Please input the node you want to add-> P Please input the parent node of P-> A Parent already has 2 children. Please select from one of the following options: 1. Add Node 2. Tree Size 3. Find Node 0. Exit ->1 Please input the node you want to add-> P Please input the parent node of P-> F Node successfully added! A B C B D E D H I H I E J K J K C F G F L P

Design Requirements The main class in your application should be named BinaryTree. This class should instantiate an instance of the second class – to be named TreeDataStructure – and that instance should be used to call the appropriate methods to generate the initial tree, display the menu to the user and exhibit the functionality described above. Apart from the main method, the BinaryTree class should also have a method to print the menu options (void printMenu() ). You can copy and paste the code below into your main class to generate the initial tree.

public static void main(String[] args) { TreeDataStructure root = new TreeDataStructure("A"); root.addChild("B", "A"); root.addChild("C", "A"); root.addChild("D", "B"); root.addChild("E", "B"); root.addChild("F", "C"); root.addChild("G", "C"); root.addChild("H", "D"); root.addChild("I", "D"); root.addChild("J", "E"); root.addChild("K", "E"); root.addChild("L", "F"); /* * * Include code here to implement required functionality. */ } The TreeDataStructure class should implement the INode interface (which is provided below). The methods addChild(), find(), printTree(), and size() in the TreeDataStructure class must be implemented recursively. NOTE: Using recursion is one of the main objectives of this assignment. A solution that does not use recursion to implement the required functionality will earn zero points. Create an interface named INode within your package (following steps similar to how you would create a class) and copy and paste the interface code below into it. public interface INode { /** * This method checks to see if the specified parent node exists in the tree. If * not, it returns false after printing an appropriate message. If the node exists, * the method checks to see if it already has two children. If it does, the method * returns false. Otherwise, it either adds the new node as the parent node’s left * child (if the parent has no children) or as the right child (if the parent * already has one child). * * @param ID new node to add * @param parentID parent node in Tree * @return true if successful, false otherwise */ public boolean addChild(String ID, String parentID); /** * This method looks within the tree to find if “value” (the ID of the node to be * found) is contained in that subtree. The node used to call the find method acts * as the root of that tree / subtree. * * @param value a string (ID of a node) to be found in the tree * * @return the node if found. */ public INode find(String value); /** * Gets the parent of this node.