Please help me code the following in JAVA

Please read the task thoroughly, and include many COMMENTS so I can understand!

Full points will be awarded, thanks in advance! CharTree driver class:

import java.io.*;

import java.util.*;

public class CharTree {

/*Inner class Node, 2 references(pointers), one data element

* The only reason this inner class is static is that it is used in

* the static methods insertInSubtree , isInSubtree , and

* showElementsInSubtree. This class should have more methods.

* This is just a sample of possible methods.

*/

private static class TreeNode {

// Declare private data type char

// Declare 2 links, rightLink & leftLink of type TreeNode

// Parametrized constructor to build a node

public TreeNode(char newData, TreeNode newLeftLink, TreeNode newRightLink) {

// complete the constructor

}

} //End of IntTreeNode inner class

// The first node of the tree, called root

private TreeNode root;

// Default constructor to build the CharTree

public CharTree( ) {

root = null;

}

// Utility methods for CharTree:

public void add(char item) {

root = insertInSubtree(item, root);

}

public boolean contains(char item) {

return isInSubtree(item, root);

}

public void showElements( ) {

showElementsInSubtree(root);

}

/**

Returns the root node of a tree that is the tree with root node

subTreeRoot, but with a new node added that contains item.

*/

private static TreeNode insertInSubtree(char item, TreeNode subTreeRoot) {

if (subTreeRoot == null)

return new TreeNode(item, null, null);

else if (item

subTreeRoot.leftLink = insertInSubtree(item, subTreeRoot.leftLink);

return subTreeRoot;

}

else { //item >= subTreeRoot.data

subTreeRoot.rightLink = insertInSubtree(item, subTreeRoot.rightLink);

return subTreeRoot;

}

}

private static boolean isInSubtree(char item, TreeNode subTreeRoot) {

// base case: is subTreeRoot null? then return false

// else if subTreeRoot.data == item what would you return?

// else item

// recursive call

//else // item >= link.data

// recursive call

}

private static void showElementsInSubtree(TreeNode subTreeRoot) { //Uses inorder traversal.

if (subTreeRoot != null) {

showElementsInSubtree(subTreeRoot.leftLink);

System.out.print(subTreeRoot.data + " ");

showElementsInSubtree(subTreeRoot.rightLink);

} //else do nothing. Empty tree has nothing to display.

}

public static void main(String[] args) {

CharTree tree = new CharTree();

tree.add('c');

tree.add('a');

tree.add('t');

tree.add('s');

showElementsInSubtree(tree.root);

}

} MorseTree class:

import java.io.File;

import java.io.FileNotFoundException;

import java.util.*;;

/*

* This class reads in data from a text file ("data.txt") and populates a binary tree with an

* ordering constraint. See the lab instructions for more information, but in general, dots go right

* and dashes go left when constructing or traversing a Morse code tree. Search for //TODO

* in the code to see what code you have to implement.

*

* Start with the constructor. In your constructor read each line in from the textfile first,

* calling add() for each {letter, morseCodeStr} pair.

*

*/

public class MorseTree {

//TODO: data member called "root" goes here

//TODO: Complete constructor

public MorseTree() {

//first, open data.txt, add each line to the tree

Scanner fin;

try {

//for each line in the file,

// get the letter(char) and the Morse string

// call add() with this data

// print out the letter and Morse string here for debugging

} catch (FileNotFoundException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

}

public void add(String morseStr, char letter) {

root = insertInSubtree(morseStr, letter, root);

}

//TODO: recursively complete this function. It's only a few characters different from findInSubtree()

private TreeNode insertInSubtree(String morseStr, char letter, TreeNode subtree) {

//base case 1 : subtree is null

//base case 2 : morseStr is of length 0

//recursive case 1: the first char in morseStr is a '.', so recursively traverse tree

//recursive case 2: the first char in the morseStr is a '-', so recurse accordingly

return subtree; //always the last line, always return the node you are working on

}

public Character translate(String morseStr) {

return findInSubtree(morseStr, root);

}

//TODO: recursively complete this function. Very similar to insertInSubtree()

private Character findInSubtree(String morseStr, TreeNode subtree) {

//base case 1 : subtree is null

//base case 2 : morseStr is of length 0

//recursive case 1: the first char in morseStr is a '.', so recursively traverse tree

//recursive case 2: the first char in the morseStr is a '-', so re-curse accordingly

return null; //remove this

}

//TODO: Non-recursive function that calls other (recursive) functions

public String translateString(String tokens) {

String retVal = "";

//build a scanner here using tokens as input

//iterate over the tokens calling translate on each token (substring separated by a space)

//concat these characters and return them

return retVal;

}

public String toMorseCode(Character c) { .

//walk the tree looking for the TreeNode with the char c in it

//preorder walk?

//inorder walk?

//postorder walk?

//when you've found the char c, report the path from the root to the node

//and build the morse code by adding a "." when you go right, "-" when you go left

return new String("You wish.");

}

public String toString() {

return inorderWalk();

}

private String inorderWalk() {

return new String("Another wish.");

}

public static void main(String[] args) {

MorseTree mt = new MorseTree(); //builds our tree using data from a file

//System.out.println(mt.translate("...")); //prints out S

//System.out.println(mt.translate("---")); //prints out O

//System.out.println(mt.translate(".......-")); //prints out null

//System.out.println(mt.translateString("... --- ...")); //SOS

//System.out.println(mt.toMorseCode('S')); //find where we are in the tree, remember path to root

}

// Inner class to create the linked structure

private class TreeNode {

Object data; // holds a given nodes data

TreeNode right;

TreeNode left;

public TreeNode() {

this.data = null;

this.right = null;

this.left = null;

}

public void setRight(TreeNode rightNode) {

this.right = rightNode;

}

public void setLeft(TreeNode leftNode) {

this.left = leftNode;

}

}

}

Summary In this lab, we will build a k-nary tree (where k2) that also maintains an ordering property. Samuel Morse's code is pictured below, where the rule is: "dashes go left" and "dots go right". Once we've built and populated our Binary Search Tree so it looks like the tree below, we will be able to traverse the tree and use it to translate a given Character ('S') or String ("SOS") into corresponding dots and dashes ("..." and "..._-...", respectively) Dash Dot START E. WR U 0 9 8 7 61 2 3 4 5 1. Warmup with CharTree & CharNode Build a small Binary Search tree that stores characters in its nodes. It should observe the class invariant that for any given node, all nodes in the left subtree are less than that node (alphabetically) and all nodes in Summary In this lab, we will build a k-nary tree (where k2) that also maintains an ordering property. Samuel Morse's code is pictured below, where the rule is: "dashes go left" and "dots go right". Once we've built and populated our Binary Search Tree so it looks like the tree below, we will be able to traverse the tree and use it to translate a given Character ('S') or String ("SOS") into corresponding dots and dashes ("..." and "..._-...", respectively) Dash Dot START E. WR U 0 9 8 7 61 2 3 4 5 1. Warmup with CharTree & CharNode Build a small Binary Search tree that stores characters in its nodes. It should observe the class invariant that for any given node, all nodes in the left subtree are less than that node (alphabetically) and all nodes in