Q1. Implement a Binary Search Tree (BST) that stores student information. Each tree node stores: student ID as the key, and student name as the value. Your BST class should have root and size as instance variables. It should also have the following methods:

Insert(int key): insert the key value at the correct position and increase the size by 1

Delete(int key): delete the key and decrees the size by 1

Search(int key): search and return the value (student name) associated with the key

Preorder(): print preorder traversal of the tree

Postorder(): print postorder traversal of the tree

printID (): this method takes a name as an argument and returns the student ID (the

key). Note that this is not a typical BST operation. You can add more parameters to the

method header if needed.

findKthsmall(int k): this method finds and returns the kth smallest key. If the tree has

less than k elements, the method returns -1. You can add instance variables to the BST class if needed. You can also pass whatever parameters you need for your method to work. [Hint: remember that inorder traversal gives us the keys in an ascending order, hence, if I want the 3rd smallest element, then the method should return the third number of the inorder traversal list].

The first three methods operate exactly the same as the methods we discussed in the class. Write a test class (Driver class) and show all the previous operations in action.