using python please help solve methods

Implement the BST class by completing the provided skeleton code in the file bst.py. Once completed, your implementation will include the following methods: add(), remove() contains(), inorder_traversal() find_min(), find_max() is_empty(), make_empty()

2. The BST class is constructed using instances of the provided BSTNode class.

3. We will test your implementation with different types of objects, not just integers. We guarantee that all such objects will have correct implementation of methods __eq__(), __lt__(), __gt__(), __ge__(), __le__(), and __str__().

4. The number of objects stored in the tree will be between 0 and 900 inclusive.

5. When removing a node with two subtrees, replace it with the leftmost child of the right subtree (i.e. the inorder successor). You do not need to recursively continue this process. If the deleted node only has one subtree (either right or left), replace the deleted node with the root node of that subtree. 6. The variables in BSTNode are not private. You are allowed to access and change their values directly. You do not need to write any getter or setter methods for them.

7. RESTRICTIONS: You are NOT allowed to use ANY built-in Python data structures and/or their methods. In case you need helper data structures in your solution, the skeleton code includes prewritten implementations of Queue and Stack classes, which are in separate files and imported in bst.py and avl.py. You are allowed to create and use objects from those classes in your implementation. You are NOT allowed to directly access any variables of the Queue or Stack classes. All work must be done only by using class methods.

8. Ensure that your methods meet the specified runtime requirements.

queue and stack code below

skeleton code with methods to solve below

import random from queue_and_stack import Queue, Stack class BSTNode: """ Binary Search Tree Node class DO NOT CHANGE THIS CLASS IN ANY WAY """ def __init__(self, value: object) -> None: """ Initialize a new BST node DO NOT CHANGE THIS METHOD IN ANY WAY """ self.value = value # to store node's data self.left = None # pointer to root of left subtree self.right = None # pointer to root of right subtree def __str__(self) -> str: """ Override string method DO NOT CHANGE THIS METHOD IN ANY WAY """ return 'BST Node: {}'.format(self.value) class BST: """ Binary Search Tree class """ def __init__(self, start_tree=None) -> None: """ Initialize new Binary Search Tree DO NOT CHANGE THIS METHOD IN ANY WAY """ self._root = None # populate BST with initial values (if provided) # before using this feature, implement add() method if start_tree is not None: for value in start_tree: self.add(value) def __str__(self) -> str: """ Override string method; display in pre-order DO NOT CHANGE THIS METHOD IN ANY WAY """ values = [] self._str_helper(self._root, values) return "BST pre-order { " + ", ".join(values) + " }" def _str_helper(self, node: BSTNode, values: []) -> None: """ Helper method for __str__. Does pre-order tree traversal DO NOT CHANGE THIS METHOD IN ANY WAY """ if not node: return values.append(str(node.value)) self._str_helper(node.left, values) self._str_helper(node.right, values) def get_root(self) -> BSTNode: """ Return root of tree, or None if empty DO NOT CHANGE THIS METHOD IN ANY WAY """ return self._root def is_valid_bst(self) -> bool: """ Perform pre-order traversal of the tree. Return False if nodes don't adhere to the bst ordering property. This is intended to be a troubleshooting method to help find any inconsistencies in the tree after the add() or remove() operations. A return of True from this method doesn't guarantee that your tree is the 'correct' result, just that it satisfies bst ordering. DO NOT CHANGE THIS METHOD IN ANY WAY """ stack = Stack() stack.push(self._root) while not stack.is_empty(): node = stack.pop() if node: if node.left and node.left.value >= node.value: return False if node.right and node.right.value  None: """ TODO: Write your implementation """ pass def remove(self, value: object) -> bool: """ TODO: Write your implementation """ pass # Consider implementing methods that handle different removal scenarios; # # you may find that you're able to use some of them in the AVL. # # Remove these comments. # # Remove these method stubs if you decide not to use them. # # Change these methods in any way you'd like. # def _remove_no_subtrees(self, remove_parent: BSTNode, remove_node: BSTNode) -> None: """ TODO: Write your implementation """ # remove node that has no subtrees (no left or right nodes) pass def _remove_one_subtree(self, remove_parent: BSTNode, remove_node: BSTNode) -> None: """ TODO: Write your implementation """ # remove node that has a left or right subtree (only) pass def _remove_two_subtrees(self, remove_parent: BSTNode, remove_node: BSTNode) -> None: """ TODO: Write your implementation """ # remove node that has two subtrees # need to find inorder successor and its parent (make a method!) pass def contains(self, value: object) -> bool: """ TODO: Write your implementation """ pass def inorder_traversal(self) -> Queue: """ TODO: Write your implementation """ pass def find_min(self) -> object: """ TODO: Write your implementation """ pass def find_max(self) -> object: """ TODO: Write your implementation """ pass def is_empty(self) -> bool: """ TODO: Write your implementation """ pass def make_empty(self) -> None: """ TODO: Write your implementation """ pass # ------------------- BASIC TESTING ----------------------------------------- if __name__ == '__main__': print(" PDF - method add() example 1") print("----------------------------") test_cases = ( (1, 2, 3), (3, 2, 1), (1, 3, 2), (3, 1, 2), ) for case in test_cases: tree = BST(case) print(tree) print(" PDF - method add() example 2") print("----------------------------") test_cases = ( (10, 20, 30, 40, 50), (10, 20, 30, 50, 40), (30, 20, 10, 5, 1), (30, 20, 10, 1, 5), (5, 4, 6, 3, 7, 2, 8), (range(0, 30, 3)), (range(0, 31, 3)), (range(0, 34, 3)), (range(10, -10, -2)), ('A', 'B', 'C', 'D', 'E'), (1, 1, 1, 1), ) for case in test_cases: tree = BST(case) print('INPUT :', case) print('RESULT :', tree) print(" PDF - method add() example 3") print("----------------------------") for _ in range(100): case = list(set(random.randrange(1, 20000) for _ in range(900))) tree = BST() for value in case: tree.add(value) if not tree.is_valid_bst(): raise Exception("PROBLEM WITH ADD OPERATION") print('add() stress test finished') print(" PDF - method remove() example 1") print("-------------------------------") test_cases = ( ((1, 2, 3), 1), ((1, 2, 3), 2), ((1, 2, 3), 3), ((50, 40, 60, 30, 70, 20, 80, 45), 0), ((50, 40, 60, 30, 70, 20, 80, 45), 45), ((50, 40, 60, 30, 70, 20, 80, 45), 40), ((50, 40, 60, 30, 70, 20, 80, 45), 30), ) for case, del_value in test_cases: tree = BST(case) print('INPUT :', tree, "DEL:", del_value) tree.remove(del_value) print('RESULT :', tree) print(" PDF - method remove() example 2") print("-------------------------------") test_cases = ( ((50, 40, 60, 30, 70, 20, 80, 45), 20), ((50, 40, 60, 30, 70, 20, 80, 15), 40), ((50, 40, 60, 30, 70, 20, 80, 35), 20), ((50, 40, 60, 30, 70, 20, 80, 25), 40), ) for case, del_value in test_cases: tree = BST(case) print('INPUT :', tree, "DEL:", del_value) tree.remove(del_value) print('RESULT :', tree) print(" PDF - method remove() example 3") print("-------------------------------") case = range(-9, 16, 2) tree = BST(case) for del_value in case: print('INPUT :', tree, del_value) tree.remove(del_value) print('RESULT :', tree) print(" PDF - method remove() example 4") print("-------------------------------") case = range(0, 34, 3) tree = BST(case) for _ in case[:-2]: root_value = tree.get_root().value print('INPUT :', tree, root_value) tree.remove(root_value) if not tree.is_valid_bst(): raise Exception("PROBLEM WITH REMOVE OPERATION") print('RESULT :', tree) print(" PDF - method contains() example 1") print("---------------------------------") tree = BST([10, 5, 15]) print(tree.contains(15)) print(tree.contains(-10)) print(tree.contains(15)) print(" PDF - method contains() example 2") print("---------------------------------") tree = BST() print(tree.contains(0)) print(" PDF - method inorder_traversal() example 1") print("---------------------------------") tree = BST([10, 20, 5, 15, 17, 7, 12]) print(tree.inorder_traversal()) print(" PDF - method inorder_traversal() example 2") print("---------------------------------") tree = BST([8, 10, -4, 5, -1]) print(tree.inorder_traversal()) print(" PDF - method find_min() example 1") print("---------------------------------") tree = BST([10, 20, 5, 15, 17, 7, 12]) print(tree) print("Minimum value is:", tree.find_min()) print(" PDF - method find_min() example 2") print("---------------------------------") tree = BST([8, 10, -4, 5, -1]) print(tree) print("Minimum value is:", tree.find_min()) print(" PDF - method find_max() example 1") print("---------------------------------") tree = BST([10, 20, 5, 15, 17, 7, 12]) print(tree) print("Maximum value is:", tree.find_max()) print(" PDF - method find_max() example 2") print("---------------------------------") tree = BST([8, 10, -4, 5, -1]) print(tree) print("Maximum value is:", tree.find_max()) print(" PDF - method is_empty() example 1") print("---------------------------------") tree = BST([10, 20, 5, 15, 17, 7, 12]) print("Tree is empty:", tree.is_empty()) print(" PDF - method is_empty() example 2") print("---------------------------------") tree = BST() print("Tree is empty:", tree.is_empty()) print(" PDF - method make_empty() example 1") print("---------------------------------") tree = BST([10, 20, 5, 15, 17, 7, 12]) print("Tree before make_empty():", tree) tree.make_empty() print("Tree after make_empty(): ", tree) print(" PDF - method make_empty() example 2") print("---------------------------------") tree = BST() print("Tree before make_empty():", tree) tree.make_empty() print("Tree after make_empty(): ", tree)