Write a java program to convert a text encoded with Morse code to an English text. First, your

program should create a binary tree of letters that are accessible by sequences of dots and dashes.

The search for a letter begins in the root, and if the current symbol is a dash, go to the left if it is a

dot, go to the right. For example, if the encoded letter is $.-($dot dash$),$ then, starting from the root, the search goes first to the right child of the root and then to this child$$s left child which contains the letter A$.$ In the file with an encoded text, separate encoded letters with a single blank and separate words with two blanks. For reading, use FileIntputStream. Store the decoded text

in a file. Using, without any changes, the BST class created in the lab, create in your program a new class, as in:

class MorseCode extends BST $\{...\}$

which should include a constructor that generates the tree. Use an array to store the Morse

codewords $($i$.$e$.,$ the sequences of dots and dashes$)$ and in the constructor use a loop to go

through this array to insert nodes to store characters corresponding to these codewords.

This is the BST class:

public class BST$>\{$

protected BSTNode root $=$ null;

public void insert$($T t$)\{$

BSTNode p $=$ root, prev $=$ null;

while $($p $!=$ null$)\{$

prev $=$ p;

if $($t$.$compareTo$($p$.$el$)<mtext></mtext><mn>0</mn><mi>)</mi>$

p $=$ p$.$left;

else

p $=$ p$.$right;

$\}$

if $($root $==$ null$)$

root $=$ new BSTNode$($t$)$;

else if $($t$.$compareTo$($prev$.$el$)<mtext></mtext><mn>0</mn><mi>)</mi>$

prev.left $=$ new BSTNode $($t$)$;

else

prev.right $=$ new BSTNode $($t$)$;

$\}$

$\}$ in a file.

Using, without any changes, the BST class created in the lab, create in your program a new class, as in:

class MorseCode extends BST $\backslash \{...\backslash \}$ which should include a constructor that generates the tree. Use an array to store the Morse codewords $($i$.$e$.,$ the sequences of dots and dashes$)$ and in the constructor use a loop to go through this array to insert nodes to store characters corresponding to these codewords. $```$

public class BST$>\{$

protected BSTNode root $=$ null;

public void insert$($T t$)[$

BSTNode p $=$ root, prev $=$ null;

while $($p $!=$ null$)\{$

prev $=$ p;

if $($t$.$compareTo$($p$.$el$)<mtext></mtext><mn>0</mn><mi>)</mi>$

p $=$ p$.$left;

else

p $=$ p$.$right;

$\}$

if $($root $==$ null$)$

root $=$ new BSTNode$($t$)$;

else if $($t$.$compareTo$($prev$.$el$)<mtext></mtext><mn>0</mn><mi>)</mi>$

prev.left $=$ new BSTNode $($t$)$;

else

prev.right $=$ new BSTNode $($t$)$;

$|$

$\}$

$```$