Objective:

The original task for this assignment was going to be to implement the BinarySearchTree $($BST$)$ ADT as presented in the textbook. After considering the textbook code it was decided that the code presented tends to obscure the basic concepts of a BST$.$ So$,$ for this assignment we will go outside the textbook and implement a more straight$-$forward version of the BST$.$

You may import the following classes if needed:

$$ Random

Step $1$:

Create a NetBeans project whose name follows the convention Lab$109-$LastFM

Implement the BinarySearchTree $($BST$)$ class found at the website listed above.

Create a Client class that implements the main method found at the website listed above to test your implementation of the BST class.

When you run the main method in your Client class you should get the same results as indicated on the website.

Step $2$:

For this step make the following modifications to the BST class.

Improve the BST class from the website listed above as follows:

$-$ Add a height method to the BST class.

$-$ Add a preorderTraversal method to the BST class.

$-$ Add a postorderTraversal method to the BST class.

$-$ Note, you do NOT need to make your BST class generic.

$-$ You can make any additional modification needed.

STEP $3$:

Test your modified BST class by having the main method in your Client class:

$-$ Create and empty BST

$-$ Insert ten $(10)$ random integer values in the range $0$ to $99$ into the BST using a seed value of $161$ for the random number generator.

o Print out each value as it is inserted into the BST so that you know the insertion order.

$-$ Print out the following:

o The height of the tree

o the preorder traversal

o the inorder traversal

o the postorder traversal

$-$ Using the printed insertion order, manually draw a picture of the BST and verify that the traversals are correct.

Step $4$:

In class we discussed the fact that the expected performance of a BST is O$($ log$($n$))$ and the worst$-$case performance of a BST is O$($ n $).$ It should be clear that the worst$-$case performance is O$($ n $)$ but let$$s show that the expected case performance is O$($ log$($n$)).$

Test your BST as follows:

$-$ Add $1$ million unique $($no repeats$)$ integers to a BST in ascending order and then determine the height of the tree.

$-$ Add $1$ million unique $($no repeats$)$ integers to a BST in descending order and then determine the height of the tree.

$-$ Add $1$ million unique $($no repeats$)$ integers to a BST in random order and determine the height of the tree.

$-$ Repeat the last step four more times with the unique integers in different random order, determining the height each time.

$-$ Note: If get a StackOverflowError determine which method is generating the error and rewrite the method so that it does not generate a StackOverflowError.

$-$ Display your results in a nicely formatted ASCII table following the example given at the end of this assignment.

o Write you ASCII table so that the column widths automatically adjust to the size of the data being displayed.

Step $5$:

Repeat Step $4$ with the following N values and generate a separate ASCII table for each value of N:

$-$ N $=100,000$

$-$ N $=50,000$

$-$ N $=1,000$

Note that you will be printing out four separate ASCII tables.

Each ASCII table should independently determine the appropriate widths for its columns.

You should consider making an AsciiTable class.

Things to turn in:

$$ Open a Microsoft Word document named using the Lab$109-$LastFM.docx convention

$$ Copy and Paste the source code of each of your classes

o Include all of the classes you created$/$transcribed for this assignment.

o Do not include classes that you copied from previous assignments.

$$ Run your client program and then copy the contents of the Output Windows to the clipboard and paste it into your Word document.

$$ Next, export your NetBeans project to a zip archive.

$$ Finally, on blackboard, submit both your Word document file and your zipped project file in one submission.parent.left $=$ newNode

in class we discussed the fact that the expected performance of a BST is $O(log(n))$ and the worst$-$case

Test your BST as follows

$//$inorder$0$ will perform inorder traversal on binary search tree

$//$Check whether tree is empty

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

System.out.println$("$Tree is empty"$)$;

else $\{$

if$($node$.$left! $=$ null$)$

inorderTraversal$($node$.$left$)$:

System.out.print$($nod if$($node$.$right! $=$ null$)$

inorderTraversal$($node$.$right:

$,$

public static void main$($String$[]$ args$)\{$ BinarySearchTree bt $=$ new BinarySearchTree$0$; $//$Add nodes to the binary tree bt$.$insert$(50)$; bt$.$insert$(30)$; bt$.$insert$(70)$; bt$.$insert$(60)$; bt$.$insert$(10)$; bt$.$insert$(90)$; System.out.printIn$("$Binary search tree after insertion:"$)$;

System.out.println"$("$Binary $//$Displays the binary tree

Node deleted Node $=$ nu

N$/$Deletes node $90$ which has

deletedNode $=$ bt$.$deleteNode$($bt$.$root, $90)$

System.out.println$(")$nBinary search tree after deleting node $90$:$"$ bt$.$inord$---------------------------------$