The objective of this assignment is to practice and implement binary search tree operations.

Problem Specification:

Write a generic Java program to create a Binary Search Tree. This Binary Search Tree is to store the integer

values. Your program should display a menu of choices to operate the Binary Search Tree data structure.

Please download BSTSample before start. See the sample menu below:

Insert a node $(15,5,16,3,12,20,10,13,18,23,6,7)($see Fig. $1$a$)$

Find a node

Delete a node $($see Fig. $1$b$,1$c$,1$d$)$

Deleting a node with no children $(13)$

Deleting a node with one child $(16)$

Deleting a node with two children $(5)$

Print preorder, inorder, and postorder traversal

$($a$)$

$($b$)$

$($c$)$

$($d$)$

Figure $1$: $($a$)$ Binary Search Tree after inserting all the values; $($b$)$ Binary Search Tree after deleting $13$; $($c$)$

Binary Search Tree after deleting $16$; $($d$)$ Binary Search Tree after deleting $5$

Please note that you will not get any credit if you do not implement generic recursive versions

of binary search tree operations with the above$-$mentioned criteria.

Consider below given classes and complete based on these classes. You are NOT allowed to change the method signatures, but feel free to add extra methods:$-$

public class DriverBST $\{$

public static void main$($String$[]$ args$)\{$

BinarySearchTree bst $=$ new BinarySearchTree$(15)$;

bst$.$insert$(5)$;

bst$.$insert$(16)$;

$//.........$

$//.........$

$//.........$

$//$ Call preorder, inorder, and postorder traversals

bst$.$delete$(13)$;

$//$ Call preorder, inorder, and postorder traversals

bst$.$delete$(16)$;

$//$ Call preorder, inorder, and postorder traversals

bst$.$delete$(5)$;

$//$ Call preorder, inorder, and postorder traversals

$\}//$ end main

$\}$

public class BinarySearchTree$>\{$

private TreeNode root;

public BinarySearchTree$()\{$

root $=$ null;

$\}//$ end default constructor

public BinarySearchTree$($T rootItem$)\{$

root $=$ new TreeNode$($rootItem$,$ null, null$)$;

$\}//$ end constructor

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

root $=$ insertItem$($root$,$ newItem$)$;

$\}//$ end insert

public T retrieve$($T searchKey$)\{$

return retrieveItem$($root$,$ searchKey$)$;

$\}//$ end retrieve

public void delete$($T searchKey$)$ throws TreeException $\{$

root $=$ deleteItem$($root$,$ searchKey$)$;

$\}//$ end delete

private TreeNode insertItem$($TreeNode tNode, T newItem$)\{$

$//$ Implement insertItem here.

$//$ The error will go away once you implement and returns an node

$\}//$ end insertItem

private T retrieveItem$($TreeNode tNode, T searchKey$)\{$

$//$ Implement retrieveItem here

$//$ The error will go away once you implement and returns an item

$\}//$ end retrieveItem

private TreeNode deleteItem$($TreeNode tNode, T searchKey$)\{$

$//$ Implement deleteItem here

$//$ The error will go away once you implement and returns a node

$\}//$ end deleteItem

public void setPreorder$()\{$

preorder$($root$)$;

$\}//$ end setPreOrder

public void setInorder$()\{$

inorder$($root$)$;

$\}//$ end setInorder

public void setPostorder$()\{$

postorder$($root$)$;

$\}//$ end setPostorder

private void preorder$($TreeNode treeNode$)\{$

$//$ implement preorder here

$\}//$ end preorder

private void inorder$($TreeNode treeNode$)\{$

$//$ implement inorder here

$\}//$ end inorder

private void postorder$($TreeNode treeNode$)\{$

$//$ implement postorder here

$\}//$ end postorder

$\}//$ end BinarySearchTree

public class TreeException extends RuntimeException $\{$

public TreeException$($String s$)\{$

super$($s$)$;

$\}//$ end constructor

$\}//$ end TreeException

public class TreeNode $\{$

T item;

TreeNode leftChild;

TreeNode rightChild;

public TreeNode$($T newItem$)\{$

$//$ Initializes tree node with item and no children.

item $=$ newItem;

leftChild $=$ null;

rightChild $=$ null;

$\}//$ end constructor

public TreeNode$($T newItem, TreeNode left, TreeNode right$)\{$

$//$ Initializes tree node with item and the left and right children references.

item $=$ newItem;

leftChild $=$ left;

rightChild $=$ right;

$\}//$ end constructor

$\}//$ end TreeNode