Here's the Starter Code:

Tree (BST). In CS, a binary search tree is used in a variety of application domains from routers to data compression. We will focus on building the simple BST to prepare us for a self-balancing binary tree such as a red-black tree. 2 Program Requirements: 2.1 Write BinarySearchTree class. You will need to write a BinarySearchTree class. To receive any credit, your class must follow the specifications below exactly: - Class Name: BinarySearchTree - Methods: * Valid Input: An integer in the bound (,+). * Error Handling: Raise a TreeIsEmpty exception if the method is called when the tree is empty. * Description: The delete method will remove a node from the tree and return True, else it will return False. When deleting a node, delete the node whose ID matches the integer id from the input parameter. * Note: Consider the following four cases for delete: - If the said node has no children: Delete it by setting both the nodes' parent pointer and the parents' corresponding child pointer to None. - If the said node has one child: Delete it by making its parent point to its child and setting all of its pointers to None. (There is a useful method in BSTNode for this). - If the said node has two children: First delete the successor. Then replace the said node's content with the successor's content. The successor of a node is the left-most node in the node's right subtree. - If the value specified by delete does not exist in the tree: Then the structure is left unchanged and the method should return False. - find ( self,id) returnValue * Complexity: O(lg(n))O(n) * Valid Input: An integer in the bound (,+). * Error Handling: Raise a TreeIsEmpty exception if the method is called when the tree is empty. * Description: This method takes an integer id and returns the tuple in the tree whose ID matches that value. If no such tuple exists in the tree, return False. - The methods listed above are the only methods that will be tested. However, you may add additional methods as you please. We have provided a skeleton code to get you started be sure to read and understand the auxiliary methods provided before you start. - Pay attention to the complexity bounds mentioned in the method descriptions. Your implementation must run within these bounds. - For this assignment you are not allowed to use a list. This assignment should be done using BSTNode which makes a tree, like how we did with the linked list in assignment 1. You are also not allowed to use any of the python built-in functions or libraries for this assignment. Everything can be done with simple python. The skeleton codes contain everything you need to implement the methods above, so you don't really need to add anything. - Warning: You are not allowed to import anything into the source file with the classes. All programs must be written in basic Python 3.8+. - You will need to make your own main for testing your code using the methodology described in the lab. Testing your own code is a very common practice in the industry. - Warning: I will be testing your code with a more robust main that will check all of the corner cases and uses a wider variety of objects. Keep this in mind while developing your data structures. You will need to use the methodology discussed in lab to figure out all corner cases and account for them. Your programs must be robust (i.e. does not crash when given bad input or told to peak/front when the stack/queue is empty etc.) - As mentioned before, please do not use method annotations. Description: A Binary Search Tree (BST). Note: Algorithms for the BST can be found in ch. 12 of the book