One of the benefits of a binary search tree is that $($if it is balanced$),$ we can find any element without visiting very many Nodes. To demonstrate this, update the findEntry method in BinarySearchTree to print how many Nodes were visited before the target item was found $($or was determined to not be in the tree$).$ Recall that findEntry is a private helper method called by contains, so in your test code you$$ll have to call contains. Note: only one value should be printed, when the search is complete.

For example: $$Search complete. $3$ Nodes visited"

Hint: You can update this method$$s number of parameters!

package TreePackage;

public class BinarySearchTree$>$ extends BinaryTree implements SearchTreeInterface

$\{$

public BinarySearchTree$()$

$\{$

$\}$

public BinarySearchTree$($T rootEntry$)$

$\{$

setRootNode$($new BinaryNode$<>($rootEntry$))$;

$\}$

@Override

public boolean contains$($T anEntry$)$

$\{$

return findEntry$($getRootNode$(),$ anEntry$)!=$ null;

$\}$

@Override

public T getEntry$($T anEntry$)$

$\{$

return findEntry$($getRootNode$(),$ anEntry$)$;

$\}$

private T findEntry$($BinaryNode rootNode, T anEntry$)$

$\{$

$//$ TODO update this method to print how many nodes were visited

T result $=$ null;

if $($rootNode $!=$ null$)$

$\{$

$//$ We are not at a base case

T rootEntry $=$ rootNode.getData$()$;

if $($anEntry$.$equals$($rootEntry$))$

$\{$

result $=$ rootEntry;

$\}$

else if $($anEntry$.$compareTo$($rootEntry$)<0)$

result $=$ findEntry$($rootNode$.$getLeftChild$(),$ anEntry$)$;

else

result $=$ findEntry$($rootNode$.$getRightChild$(),$ anEntry$)$;

$\}$

return result;

$\}$

@Override

public T add$($T anEntry$)$

$\{$

T result $=$ null;

if $($isEmpty$())$

$\{$

$//$ Tree is empty, add 'anEntry' to the root

setRootNode$($new BinaryNode$<>($anEntry$))$;

$\}$

else

$\{$

$//$ Tree is not empty, recursively find the location of the new node

result $=$ addEntry$($getRootNode$(),$ anEntry$)$;

$\}$

return result;

$\}$

private T addEntry$($BinaryNode rootNode, T anEntry$)$

$\{$

T result $=$ null;

$//$ compare anEntry and rootNode's data

int comparison $=$ anEntry.compareTo$($rootNode$.$getData$())$;

if $($comparison $==0)$

$\{$

result $=$ rootNode.getData$()$;

rootNode.setData$($anEntry$)$;

$\}$

else if $($comparison $<0)$

$\{$

$//$ anEntry is 'less than' rootNode.getData. Move left

if $($rootNode$.$hasLeftChild$())$

$\{$

$//$ rootNode has a left child, so we can actually move left

result $=$ addEntry$($rootNode$.$getLeftChild$(),$ anEntry$)$;

$\}$

else

$\{$

$//$ rootNode has no left child but 'anEntry' belongs to rootNode's left

$//$ Create a new BinaryNode to be its left child

rootNode.setLeftChild$($new BinaryNode$<>($anEntry$))$;

$\}$

$\}$

else

$\{$

$//$ anEntry is 'greater than' rootNode.getData. Move right

if $($rootNode$.$hasRightChild$())$

$\{$

$//$ rootNode has a right child, so we can actually move right

result $=$ addEntry$($rootNode$.$getRightChild$(),$ anEntry$)$;

$\}$

else

$\{$

rootNode.setRightChild$($new BinaryNode$<>($anEntry$))$;

$\}$

$\}$

return result;

$\}$

@Override

public T remove$($T anEntry$)$

$\{$

return null;

$\}$

@Override

public void setTree$($T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree$)$

$\{$

throw new UnsupportedOperationException$("$Binary search trees do not support the 'setTree' method!"$)$;

$\}$

$\}$

$///////$

package TreePackage;

import java.util.Iterator;

import java.util.NoSuchElementException;

public class BinaryTree implements BinaryTreeInterface

$\{$

private BinaryNode root;

protected BinaryNode getRootNode$()$

$\{$

return root;

$\}$

protected void setRootNode$($BinaryNode newRoot$)$

$\{$

root $=$ newRoot;

$\}$

public BinaryTree$()$

$\{$

root $=$ null;

$\}$

public BinaryTree$($T rootData$)$

$\{$

root $=$ new BinaryNode$<>($rootData$)$;

$\}$

public BinaryTree$($T rootData, BinaryTree leftTree, BinaryTree rightTree$)$

$\{$

initializeTree$($rootData$,$ leftTree, rightTree$)$;

$\}$

@Override

public void setTree$($T rootData$)$

$\{$

setTree$($rootData$,$ null, null$)$;

$\}$

@Override

public void setTree$($T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree$)$

$\{$

initializeTree$($rootData$,($B