In recursively defined structures, like trees, all the coding $($and

complexity$)$ is found in the recursive structure itself. So$,$ for this

assignment, all the logic will be found in the Node Class.

The Tree Class, which is defined in the handout below, merely starts

recursion on the root.

$\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

public class Node

Node$($int key, string value$)$ Constructor.

Node left

Node right

int key The key to find the value.

string value The value that the node contains.

string toTree$($String label, int indent$)$ Returns a string of the tree$$s structure. Please see below.

String toSortedList$()$ Returns a string sorted by the key. Please see below.

void add$($int key, string value$)$ Adds the key to the correct position in the BST$.$ If the key

already exists, do nothing.

string find$($int key$)$ Finds a node with the key and returns its value. If the

node is not found, you can return an empty string.

$\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

BinarySearchTree Class

Interface

For this project, you are also to create a wrapper BinarySearchTree Class. In reality, this class doesn't do that much. The

class simply starts recursion of the root itself.

Naturally, there is some logic needed to handle an null root, but that is just a few basic if$-$statements.

public class BinarySearchTree

BinarySearchTree$()$ Constructor.

Node root Private

string about$()$ Returns text about you $$ the author of this class.

string toTree$()$ Returns a string of the tree$$s structure.

It will start recursion from the root node with indent $0$ and a label of

"Root".

String toSortedList$()$ Returns a string sorted by the key. Please see below.

It will start recursion from the root node.

void add$($int key, String value$)$ Adds the key to the correct position in the BST$.$ If the key already

exists, do nothing.

string find$($int key$)$ Finds a node with the key and returns the value. If the node is not

found, you can return an empty string.

$\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

Binary Search Trees are extremely sensitive to the order that data is fed into them. In fact, once node is added, it's position in

the tree will never change. In the example below, I've added the same entries, but I have switched the position of the first two.

File: halloween calories $2.$txt

$60$

Tootsie Pop

$73$

M&M$\text{'}$s Fun size

$40$

Starburst Fun Size

$70$

Kit Kat Snack Size

$30$

Laffy Taffy

$80$

Snickers Fun Size

$50$

Nerds Mini Box

$77$

Hershey's Milk Chocolate Fun Size

$82$

Almond Joy Snack Size

$0$

END

Observe that, this minor change of order, has had a profound impact on the structure of the tree. The first key added will

always become the root. And it will remain the root.

$-$: $(60)$ Tootsie Pop

L: $(40)$ Starburst Fun Size

L: $(30)$ Laffy Taffy

R: $(50)$ Nerds Mini Box

R: $(73)$ M&M$\text{'}$s fun size

L: $(70)$ Kit Kat Snack Size

R: $(80)$ Snickers Fun Size

L: $(77)$ Hershey's Milk Chocolate Fun Size

R: $(82)$ Almond Joy Snack Size

$\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

Can I ask for your help? In java Programming will it be alright to code that will result in halloween text file. Please include comments and picture of the result thank you.