$//$ Implement a BinarySearchTree class using the linked structure.

$//$ Hint: The implementation of binary tree with linked structure are provided $($LinkedBinaryTree$.$java and BTNode.java$).$

$//$

$//$ The output should be:

$//$

$//=============================$ Test BinarySearchTree

$//$ Size of the tree: $6$

$//$ Height of the tree: $3$

$//$ inOrder: $124689$

$//------------------$ Test search

$//4$ with parent $2$ and leftChild: null and rightChild: null

$//------------------$ Test insert

$//1245689$

$//------------------$ Test delete

$//---------$before delete$()$

$//1245689$

$//125689$

$//------------------$ Test delete

$//---------$before delete$()$

$//1235689$

$//---------$after delete$()$

$//125689$

$//5$ with parent $1$ and leftChild: $2$ and rightChild: $8$

$//2$ with parent $5$ and leftChild: null and rightChild: null

$//1$ with parent null and leftChild: null and rightChild: $5$

$//$

$//===============================================$ Note

$//$

$//1.$ DO NOT DELETE ANY COMMENT!!!

$//2.$ Modify the file name to "BinarySearchTree.java" before compiling it$.$

$//$

$//===============================================$

public class BinarySearchTree$>$ extends LinkedBinaryTree $\{$

public BinarySearchTree$($BTNode root$)\{$

super$($root$)$;

$\}$

$/*$ It is the search method. $*/$

public BTNode search$($E key$)\{$

BTNode current $=$ this.getRoot$()$;

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

if$($key$.$compareTo$($current$.$getElement$())==0)\{$

return current;

$\}$else if$($key$.$compareTo$($current$.$getElement$())<0)\{$

current $=$ current.getLeftChild$()$;

$\}$else$\{$

current $=$ current.getRightChild$()$;

$\}$

$\}$

System.out.println$("$Did not find the key!"$)$;

return null;

$\}$

$/*$ It is the insert method. $*/$

public void insert$($BTNode node$)\{$

if$($getRoot$()==$ null$)\{$

setRoot$($node$)$;

return;

$\}$

BTNode current $=$ getRoot$()$;

BTNode parent;

while$($true$)\{$

parent $=$ current;

if $($node$.$getElement$().$compareTo$($current$.$getElement$())==0)\{$

$//$ do nothing

System.out.println$("$Node$"+$ node.getElement$().$toString$()+$ "exists!"$)$;

break;

$\}$ else if $($node$.$getElement$().$compareTo$($current$.$getElement$())<0)\{$

current $=$ current.getLeftChild$()$;

if$($current $==$ null$)\{$

parent.setLeftChild$($node$)$;

break;

$\}$

$\}$ else $\{$

current $=$ current.getRightChild$()$;

if$($current $==$ null$)\{$

parent.setRightChild$($node$)$;

break;

$\}$

$\}$

$\}$

$\}$

$/*$ It is the delete method. $*/$

public void delete$($BTNode node$)\{$

BTNode target $=$ this.search$($node$.$getElement$())$;

if $($target $==$ null$)\{$

System.out.println$("$Did not find the target!"$)$;

return;

$\}$

$//$ realDeletedNode is the node we actually delete.

BTNode realDeletedNode $=$ this.getRealDeletedNode$($target$)$;

$//$ System.out.println$($target$.$toString$())$;

$//$ System.out.println$($realDeletedNode$.$toString$())$;

if $($realDeletedNode $==$ getRoot$())\{$

setRoot$($null$)$;

return;

$\}$

$//$ delete the realDeletedNode

$//$ COMPLETE THIS BLOCK

$//$ replace the target with the realDeletedNode

$//$ COMPLETE THIS BLOCK

$\}$

public BTNode getRealDeletedNode$($BTNode deleleNode$)\{$

BTNode realDeletedNode $=$ deleleNode;

$//$ find the smallest key in the right subtree

if $($deleleNode$.$getRightChild$()!=$ null$)\{$

$//$ COMPLETE THIS BLOCK

$\}$ else if $($deleleNode$.$getLeftChild$()!=$ null$)\{$

$//$ find the largest key in the left subtree

$//$ COMPLETE THIS BLOCK

$\}$ else $\{$

$//$ do nothing

$\}$

return realDeletedNode;

$\}$

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

$//------------$ test BinarySearchTree

System.out.println$("=============================$ Test BinarySearchTree"$)$;

$//$

$//----------------------------------$

$//6$

$///\backslash$

$//29$

$///\backslash /\backslash$

$//148$ null

$//$

BTNode node$1=$ new BTNode$(1,$ null, null$)$;

BTNode node$4=$ new BTNode$(4,$ null, null$)$;

BTNode node$8=$ new BTNode$(8,$ null, null$)$;

BTNode node$2=$ new BTNode$(2,$ node$1,$ node$4)$;

BTNode node$9=$ new BTNode$(9,$ node$8,$ null$)$;

BTNode node$6=$ new BTNode$(6,$ node$2,$ node$9)$;

node$1.$setParent$($node$2)$;

node$4.$setParent$($node$2)$;

node$2.$setParent$($node$6)$;

node$8.$setParent$($node$9)$;

node$9.$setParent$($node$6)$;

BinarySearchTree tree $=$ new BinarySearchTree$($node$6)$;

System.out.println$("$Size of the tree: $"+$ tree.size$($tree$.$getRoot$()))$;

System.out.println$("$Height of the tree: $"+$ tree.height$($tree$.$getRoot$()))$;

System.out.print$("$

inOrder: $")$;

tree.inOrder$($tree$.$getRoot$())$;

System.out.println$("$

$")$;

$//-----------------------$ test search

System.out.println$("------------------$ Test search"$)$;

System.out.println$($tree$.$search$(4).$toString$())$;

System.out.println$("$

$")$;

$//----$