Welcome to Lesson 12!Learning ObjectivesBy the end of this class, you should know...How do you implement the recursive BST operationssearchminimumremove1. Searching a BSTSearching a BST is an almost identical process to inserting a new node to the tree.Let's review BST insert using an example, and then compare it to BST search:We can thus adapt the insert pseudocode for search.However, search returns a boolean to indicate whether the value was found, whereas insert is a void method.Pseudocode for search helper(node, value)1. Base Case: the value is equal to the node's data1a. return true2. Check if the value is smaller than the node's data.2a. If this is true2aa. If node's leftchild is null2aaa. return false. The value was not found2b. If the node's leftchild is not null2bb. recursively call the search helper method passing it node's leftchild and value3. Otherwise3a. Check if the node's rightchild is null3aa. If this is true, return false. The value was not found.3b. If the node's rightchild is not null3bb. recursively call the search helper method passing it node's rightchild and value1.1. Writing the BST Search MethodBelow is the code for the public search wrapper method    public boolean search(T data) {        if(root == null) {            return false;        } else {            return search(data, root);        }    }It is your job to write the helper method for search in your upcoming Lab.2. Finding the Minimum Value in a BSTThe purpose of the minimum method is to find the minimum value in the tree.Where is the minimum value always located in a Binary Search Tree?If you are uncertain, look at an example of BST to see where the minimum is located.To find the minimum, all we need to do is to scroll through the nodes in the tree to the proper location.Pseudocode for private minimum helper (Node node)If the node's leftchild is not nullreturn recursive call to minimum, passing it node's leftchildOtherwiseReturn the node's data3. Removing a Value from a BSTRemove is perhaps the most challenging BST algorithm to implement.Like search, insert, and the tree traversals it is also recursive.Remove works by first searching for a particular value in a BST. Once the node has been located, it can then be removed.However, complication comes from the fact that we could encounter several different cases:Case 1: The node we wish to remove if a leaf node <-- easy caseCase 2: The node we wish to remove has only one child <-- medium caseCase 3: The node we wish to remove has two children <-- hard caseWhen deleting nodes in each of these cases, you must be mindful to preserve the BST property.Let's look at each of these possibilities in the diagram below:image source.Therefore, when writing remove, we need to handle all three cases.Pseudocode for remove helper(node, value)1. If node is null1. return node2. Otherwise, if value < the node's data1.set node's leftchild equal to the recursive call of remove helper on node's leftchild3. Otherwise, if value > the node's data1. set node's rightchild equal to the recursive call of remove helper on node's rightchild4. Otherwise,1. If node is a leaf node1. Set node to null2. Otherwise if node has a leftchild but no rightchild1. set the leftchild to be the node3. Otherwise if node has a rightchild but no leftchild1. set the rightchild to be the node4. Otherwise1. Search for the minimum value in the right subtree of the node2. Set the node's data to be the minimum value in the node's right subtree3. Set node's rightchild equal to the recursive call of remove helper, passing it node's rightchild and the minimum data of node's right subtree (i.e. delete the duplicate value in the right subtree)5. return the node3.1 Writing BST RemoveBelow is the signature for the public remove method (wrapper).Note that the private minimum method can be used as a helper inside of the private remove method./**     * Removes a value from the BST     * @param data the value to remove     * @precondition !isEmpty()     * @precondition the data is located in the tree     * @throws NoSuchElementException when the     * precondition is violated     */    public void remove(T data) throws NoSuchElementException{}3.2. Reflection: Tracing BST RemoveRedraw the below BSTs after the indicated value has been removed.Make sure to draw any intermediary steps.BST 1: Remove 18BST 2: RemoveBST 3: Remove 15How to trace the removal processing using the given remove pseudocode:The first 3 steps in the pseudocode locate the value to remove inside the tree, and reset connections:1. If node is null //you have gone past the leaf, therefore value not in tree1. return node //or return null2. Otherwise, if value < the node's data //search to the left1.set node's leftchild equal to the recursive call of remove helper on node's leftchild //reset left connection3. Otherwise, if value > the node's data //search to the right1. set node's rightchild equal to the recursive call of remove helper on node's rightchild //reset right connection4. Otherwise, //you found it! Now time to remove!Step 4 handles removal according to the three cases (easy, medium and hard).1. If node is a leaf node //easy1. Set node to null2. Otherwise if node has a leftchild but no rightchild //medium 11. set the leftchild to be the node3. Otherwise if node has a rightchild but no leftchild //medium 21. set the rightchild to be the node4. Otherwise //hard1. Search for the minimum value in the right subtree of the node2. Set the node's data to be the minimum value in the node's right subtree3. Set node's rightchild equal to the recursive call of remove helper, passing it node's rightchild and the minimum data of node's right subtree (i.e. delete the duplicate value in the right subtree)Note that this method returns a node - Why? The method recursively re-sets connections within the tree Unlike search or insert - where we are at the level of the parent looking down to a child - when removing, we are at the level of the child node. With no pointers from child back to parent, we must use recursion to help rebuild the tree after removing an element.The connections get re-built from the node that was removed all the way back up to the root node.Wrap UpAnswer the practice exam questions on Canvas for today's lesson~Have a Great Weekend!~