This should be in Java

*Update*

3. Design and implement the TreeMaster class: The add method should be a recursive method based on the pseudocode given in the notes. This will be similar to the LinkedList example I went over in class. TreeMaster should use Generics. One data member (or attribute) in this class it should be a reference variable to point to the root. No DUMMY variables needed like the linked list example. You only add in order so there doesn't need to be the additional add methods, just one method to insert Dogs into the tree. . You will need a remove method which will also be based on the pseudocode algorithm given during class. This class will need three print methods, inorder, preorder, postorder. Use the algorithms in the notes that I covered in class to create these print methods. Preorder: Visit root node, traverse TL, traverse TR Inorder: Traverse TL, visit root node, traverse TR Postorder: Traverse TL, Traverse TR, visit root node Algorithm for Preorder Traversal 1. if the tree is empty Return else Visit the root. Preorder traverse the left subtree. Preorder traverse the right subtree. Algorithm for Inorder Traversal 1. if the tree is empty 2. Return else Inorder traverse the left subtree. Visit the root. S. Inorder traverse the right subtree. Algorithm for Postorder Traversal 1. if the tree is empty Return el se 3. Postorder traverse the left subtree. Postorder traverse the right subtree. Visit the root. ci Recursive Algorithm for Insertion in a Binary Search Tree 1. if the root is null Replace empty tree with a new tree with the item at the root and return true. else if the item is equal to root. data The item is already in the tree; return false. else if the item is less than root. data Recursively insert the item in the left subtree. else Recursively insert the item in the right subtree. ON Recursive Algorithm for Removal from a Binary Search Tree 1. if the root is null 2. The item is not in tree - return null. 3. Compare the item to the data at the local root. if the item is less than the data at the local root Return the result of deleting from the left subtree. else if the item is greater than the local root Return the result of deleting from the right subtree. else // The item is in the local root Store the data in the local root in deletedReturn. if the local root has no children Set the parent of the local root to reference null. else if the local root has one child Set the parent of the local root to reference that child. else // Find the inorder predecessor 15. if the left child has no right child it is the inorder predecessor Set the parent of the local root to reference the left child. 17. else Find the rightmost node in the right subtree of the left child. Copy its data into the local root's data and remove it by setting its parent to reference its left child. 12. 13 14 16. 3. Design and implement the TreeMaster class: The add method should be a recursive method based on the pseudocode given in the notes. This will be similar to the LinkedList example I went over in class. TreeMaster should use Generics. One data member (or attribute) in this class it should be a reference variable to point to the root. No DUMMY variables needed like the linked list example. You only add in order so there doesn't need to be the additional add methods, just one method to insert Dogs into the tree. . You will need a remove method which will also be based on the pseudocode algorithm given during class. This class will need three print methods, inorder, preorder, postorder. Use the algorithms in the notes that I covered in class to create these print methods. Preorder: Visit root node, traverse TL, traverse TR Inorder: Traverse TL, visit root node, traverse TR Postorder: Traverse TL, Traverse TR, visit root node Algorithm for Preorder Traversal 1. if the tree is empty Return else Visit the root. Preorder traverse the left subtree. Preorder traverse the right subtree. Algorithm for Inorder Traversal 1. if the tree is empty 2. Return else Inorder traverse the left subtree. Visit the root. S. Inorder traverse the right subtree. Algorithm for Postorder Traversal 1. if the tree is empty Return el se 3. Postorder traverse the left subtree. Postorder traverse the right subtree. Visit the root. ci Recursive Algorithm for Insertion in a Binary Search Tree 1. if the root is null Replace empty tree with a new tree with the item at the root and return true. else if the item is equal to root. data The item is already in the tree; return false. else if the item is less than root. data Recursively insert the item in the left subtree. else Recursively insert the item in the right subtree. ON Recursive Algorithm for Removal from a Binary Search Tree 1. if the root is null 2. The item is not in tree - return null. 3. Compare the item to the data at the local root. if the item is less than the data at the local root Return the result of deleting from the left subtree. else if the item is greater than the local root Return the result of deleting from the right subtree. else // The item is in the local root Store the data in the local root in deletedReturn. if the local root has no children Set the parent of the local root to reference null. else if the local root has one child Set the parent of the local root to reference that child. else // Find the inorder predecessor 15. if the left child has no right child it is the inorder predecessor Set the parent of the local root to reference the left child. 17. else Find the rightmost node in the right subtree of the left child. Copy its data into the local root's data and remove it by setting its parent to reference its left child. 12. 13 14 16