RECURSIVE BST OPERATIONSwith more Java generics1Let’s implement a BST class, avoiding iteration.This will give us more practice with trees, and w ith rec ursion.It will also give us a chance for a continued example with more of the “gener-ics” introduced in Java 1.5. We’ll supply comments on generics where weneed to do something more c omplicated than usual. Here are some pointsabout gene rics that might be helpful:• “class Foo<T>” introduces a class with a type parameter T.• “<T extends Bar>” introduces a type parameter that is required to be adescendant of the class Bar — with Bar itself a possibility. In a typeparameter, “extends” is also used to mean “implements”.• “<? extends Bar>” is a type paramete r that can be any class that extendsBar. The differenc e between this and the previous type parameter is thatin the previous one we were going to use T later, whereas here we’ll nevermention the type again.• “<? super Bar>” is a ty pe parameter that can be any class that is anancestor of Bar (including, again, Bar itself).• You can also have generic methods (as well as generic classes). Oddly,the type parameter for a generic method goes before the return type inthe method header, like this:public static <T> void methName(T data) { ...2Interface for our BST ClassOur BST is a tree, and thus can be implemented in a number of ways. sowe make BST an interface.A BST holds its elements in order, so we use Comparable as the type of thoseelements. Then we can build BSTs containing any orderable type of object.interface BST<E extends Comparable<? super E>> {// The element type in a BST must be Comparable, so that we can// run searches. However, it may have inherited the compareTo(),// so it’s Comparable<? super E>, not just Comparable<E>./** Insert k into me, if it’s not already there. */public void insert(E k);/** Delete k from me, if it’s there. */public void delete(E k);/** Print the contents of me, in order. */public void inorderPrint();/** Return whether I contain k. */public boolean contains(E k);}3Implementation DecisionsData StructureWe use obje cts and references to represent the nodes and edges of a tree.Because which node is the root of a tree can change, we make two classes:one for tree nodes, and one to refer to the root. (We used the same approachwith linked lists.)For the nodes, we can use the same BSTNode class as on an earlier slide.class BSTNode<T> {// Unlike BST, BSTNode does not require its data to be Comparable,// and we expect all the BSTNodes in any actual tree to be of the// same type, so the type parameter is simply T.public T key;public BSTNode<T> left;public BSTNode<T> right;public BSTNode(T key) {this.key = key;}}Because of our implementation, we call the class that acts as the treeLinkedBST.4Data MembersWe need only one data member inside our LinkedBST class.public class LinkedBST<E extends Comparable<? super E>> implements BST<E> {// Notice that we have to implement BST<E>, and not just BST.private BSTNode<E> root;/** Insert k into me, if it’s not already there. */public void insert(E k) { ... }/** Delete k from me, if it’s there. */public void delete(E k) { ... }/** Print the contents of me, in order. */public void inorderPrint() { ... }/** Return whether I contain k. */public boolean contains(E k) { ... }... maybe others ...}5The contains methodWhat is our “basic strategy” (step 1 from “Writing a Recursive Method”)?What is the “flow of information”?The method that searches a subtree must know the root of that subtree.There are (at least) two ways to implement this method:1. As a static method in LinkedBST, passing the root BSTNode as a parameter.2. As an instance method in BSTNode, calling it on the root BSTNode.We take the first approach.The contains method in BST doesn’t have a node parameter since that’s animplementation detail. So we make a helper method.Now, develop the code using the remaining steps.6The code/** Return whether I contain k. */public boolean contains(E k) {return contains(root, k);}/** Return whether k is in the tree rooted at t. */private static <T extends Comparable<? super T>> boolean contains(BSTNode<T> t,T k) {// Notice the type parameter, which is independent of the class parameter E.if (t == null) {return false;} else if (k.compareTo(t.key) == 0) {return true;} else if (k.compareTo(t.key) < 0) {return contains(t.left, k);} else { // k.compareTo(t.key) > 0return contains(t.right, k);}}Question: Why did we make contains(BSTNode<T>, T) static, but not contains(E)?Question: Can this be written elegantly with only iteration?Exercise: Write contains without using an if statement.7The insert methodDesignWe insert an element at the point where we ‘fall off’ the tree looking for it.To insert k into tree t:• If t is empty, replace t by a tree consisting of a single node with value k.• If t has k at its root, k is already in t. Return without modifying t.• If k is less than the value at the root of t, insert k into the left subtreeof t.• If k is greater than the value at the root of t, insert k into the rightsubtree of t.Inserting a node requires a change to its parent. In our recursion, we’ll passinformation back to the parent so it can change itself.8The code/** Insert k into me, if it’s not already there. */public void insert(E k) {root = insert(root, k);}/** Insert k into the tree rooted at t, and* return the root of the resulting tree. */private static <T extends Comparable<? super T>> BSTNode<T> insert(BSTNode<T> t,T k) {if (t == null) {t = new BSTNode<T>(k);} else if (k.compareTo(t.key) < 0) {t.left = insert(t.left, k);} else if (k.compareTo(t.key) > 0) {t.right = insert(t.right, k);} // else equal, don’t do anything to t.return t;}9Questions:• Why does the statement “t = new BSTNode<T>(k)” have an effect?• We pass and return the reference t. How often during the recursion doesit actually change in-between pass and return?Exercises:• Write a non-recursive insertion method f or binary search tree s.• Write a recursive version that doesn’ t return a BSTNode, but instead looksahead to se e if there’ s a child.• Write a recursive version that doesn’t return a BSTNode, but instead passesinformation about the parent to the child in the recursive call.10The Delete OperationDesign• Find the node you wish to delete (if it is there).• If the node is a leaf, de le te it.• If the node has exactly one child, delete the node by