Overview Pseudocode

Your Node class should be as follows:public int keypublic Node left. $.$ All your methods go here

end classAdding to the Tree

To add a key, you will write a recursive method that will either recurse to the left or right $-$ depending on the key. Whenever it

can no longer recurse left or right, a new node is simply added.if key $$ this node's key then create a new left child for this node. left.add$($key$,$ value$)$end if if right is null else end ifend method Creating the ASCII Tree

The method will recursively generate a string for the structure of the tree. One node will be displayed per line. In the examples

below, I$\text{'}$m using spaces followed by label that identifies each as either $"$L$"$ for left and $"$R$"$ for right. You can use spaces,

dashes, etc... You can use any size of indentation you like $(2,3,$ etc...$).$

Notice that the current node "this" is concatenated before the left and right recursive calls. This is an example of an preorder

depth$-$first traversal.Declare String resultresult $+=$ label $+"$: $"$if left isn't nullend if result $+=$ right.toString$("$R$",$ indent $+1)$return result

End FunctionThe following could be produced by this algorithm. Your version is can look a bit different if you wish, but you must indent your

lines and $($somehow$)$ indicate which is the left and right branch. Notice that this is the point of the label field.L: $(1869)$ Transcontinental Railroad L: $(1846)$ Bear Flag Revolt R: $(1911)$ California Flag officially adopted L: $(1968)$ Intel Founded Part $2$: 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.

Pseudocodeprivate Node root if root is null else end if$...$ and so on$.$

end classPart $3$: Input File Format

A number of test files will be provided to you for testing your code. The format is designed to be easy to read in multiple

programming languages. You need to use the classes, built in your programming language, to read the source files.

File Format

The first line of the data contains the total digits in the key. You might want to save this value $-$I can be used to separate the

key from the value $($using the substring function found in most programming languages$).$Key $2,$ Value $2$

$..$

Key n$.$ Value nThe following is one of the most basic test files on the website.

File: california.txt

$1947,$ Sacramento State

$1976,$ Apple Founded

$1869,$ Transcontinental Railroad

$2003,$ Tesla Founded

$1848,$ Gold Rush Begins

$1911,$ California Flag officially adopted

$1850,$ California joins the U$.$S$.$

$1968,$ Intel Founded

For this assignment, you are to create a very basic Binary Search Tree $($BST$).$ It will read data from a file $-$ which are a slightly modified version from Project #$1.$ Once loaded, your BST can print the tree as both a sorted list and an ASCII$-$art tree.

You don't have to balance the tree. In fact, don't even try it yet. Though, to be honest, a red$-$black tree $($as long as you do the left$-$child rotate trick when adding$),$ isn't all that hard.

Part $1$: Node Class

Interface

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.

$\backslash$table$[[,$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$,$toString$($String label, int indent$),$Returns a string of the tree's structure. Please see below.$],[\backslash$table$[[$void$]],$add$($int key, string value$),\backslash$table$[[$Adds the key to the correct position in the BST$.$ If the key$],[$already exists, do nothing.$]]]]$