Now that we have the ability to create a binary search tree (using the insert method) and we can use the traversal methods to verify that the nodes are created in the correct order, we can now implement functionality to find a MyBinarySearchTreeNode<T> for a given item of type T.
Create a public method called find that takes as a single parameter an instance of the Object class called obj. This method should recursively search through the BST until it finds the MyBinarySearchTreeNode<T> child that contains an item whose compareTo is 0 for the Object obj passed into the find method. If no such node is found, the method should return null.
This method is equivalent to the contains method discussed in the lecture, except it returns the MyBinarySearchTreeNode<T> containing the item we are searching for, instead of returning a boolean value. The pseudocode is:
this.item with the argument obj. If they are the same, return the current node.obj is less than this.item, then obj would be stored somewhere to the left of the current node. If the current node has a left child, recursively call the find method on the left child and return the node that the recursive call returns. If the current node has no left child, then obj is not part of the BST and we can return null.obj is greater than this.item, then do the same as Step 2 but instead consider the right of the current node.ReadMe
You might have asked yourself why our find method takes a parameter of type Object instead of type T since all of the items in the tree have type T.
The reason is because our items could themselves contain many pieces of information and the item’s compareTo method could allow us to match an item by several of those pieces of information. For example, in our ContactApp application in Lab 3 we might want to find Contact items simply by searching for the contact’s name. In such a case, we do not want to have to pass the complicated type (e.g., a Contact object) but instead something simpler (e.g., a String name).
In the application part of this lab, we will store a complex type BookLookup in our BST that contains information about the authors, title, publisher, and ISBN of books, and we want to be able to search for books based on any of those characteristics.
You should create unit tests verifying the correctness of your find method. As a suggestion, you could create a tree (e.g., the one you created for testing your insert method or any of the three traversal methods) then test whether find returns the correct node for each item in the BST. As a second test, you could try searching for items not in the BST to make sure the find method returns null when appropriate.
Don’t forget to frequently save your progress to GitHub using the add/commit/push commands with git.