Please help complete the Python program which implements a BST class by completing the instructions in the unfinished functions, thank you!:

-----------------------------------------------------------------------------------------------------------------------------------------------

#bst.py

import random from queue_and_stack import Queue, Stack from typing import Optional, Tuple 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 < node.value: return False stack.push(node.right) stack.push(node.left) return True # ------------------------------------------------------------------ # def add(self, value: object) -> None: new_node = BSTNode(value) if self._root is None: self._root = new_node return current_node = self._root while current_node is not None: if value <= current_node.value: if current_node.left is None: current_node.left = new_node return current_node = current_node.left else: if current_node.right is None: current_node.right = new_node return current_node = current_node.right def remove(self, value: object) -> bool: node, parent = self._find_node_and_parent(value) if node is None: return False if node.left is None and node.right is None: self._remove_no_subtrees(parent, node) elif node.left is not None and node.right is not None: self._remove_two_subtrees(parent, node) else: self._remove_one_subtree(parent, node) return True def _remove_no_subtrees(self, remove_parent: BSTNode, remove_node: BSTNode) -> None: if remove_parent is None: self.root = None elif remove_parent.left == remove_node: remove_parent.left = None else: remove_parent.right = None def _remove_one_subtree(self, remove_parent: BSTNode, remove_node: BSTNode) -> None: if remove_parent is None: if remove_node.left is not None: self.root = remove_node.left else: self.root = remove_node.right elif remove_parent.left == remove_node: if remove_node.left is not None: remove_parent.left = remove_node.left else: remove_parent.left = remove_node.right else: if remove_node.left is not None: remove_parent.right = remove_node.left else: remove_parent.right = remove_node.right def _remove_two_subtrees(self, remove_parent: BSTNode, remove_node: BSTNode) -> None: successor, successor_parent = self._find_inorder_successor_and_parent(remove_node) remove_node.value = successor.value if successor.left is None and successor.right is None: self._remove_no_subtrees(successor_parent, successor) else: self._remove_one_subtree(successor_parent, successor) def _find_node_and_parent(self, value: object) -> Tuple[BSTNode, Optional[BSTNode]]: """ Finds the node with the given value in the tree and returns the node and its parent """ node = self.root parent = None while node is not None and node.value != value: parent = node if value < node.value: node = node.left else: node = node.right return node, parent def _find_inorder_successor_and_parent(self, node: BSTNode) -> Tuple[BSTNode, Optional[BSTNode]]: """ Finds the inorder successor of the given node and its parent """ parent = None successor = node.right while successor.left is not None: parent = successor successor = successor.left return successor, parent def contains(self, value: object) -> bool: """ Method that returns True if value is in the tree, otherwise False. If tree is empty method returns False. Implement 0(N) runtime complexity """ pass def inorder_traversal(self) -> Queue: """ Method that perfroms an inorder traversal of the tree, and returns a Queue object that contains values of the visited nodes, in order they were visited. If tree is empty, method returns empty Queue Implement with 0(N) runtime complexity """ pass def find_min(self) -> object: """ Method returns lowest value in the tree. If empty return None. Implement 0(N) runtime complexity """ pass def find_max(self) -> object: """ Method returns the highest value in the tree. If empty return None. Implement 0(N) runtime complexity """ pass def is_empty(self) -> bool: """ Method returns True is tree is empty. Otherwise returns False. Implement 0(1) runtime complexity. """ pass def make_empty(self) -> None: """ Method removes all nodes from the tree. Implement 0(1) runtime complexity """ pass

---------------------------------------------------------------------------------------------------------------------------------

#queue_and_stack.py

class Queue: """ Class implementing QUEUE ADT. Supported methods are: enqueue, dequeue, is_empty DO NOT CHANGE THIS CLASS IN ANY WAY YOU ARE ALLOWED TO CREATE AND USE OBJECTS OF THIS CLASS IN YOUR SOLUTION """ def __init__(self): """Initialize empty queue based on Python list.""" self._data = [] def enqueue(self, value: object) -> None: """Add new element to the end of the queue.""" self._data.append(value) def dequeue(self): """Remove element from the beginning of the queue and return its value.""" return self._data.pop(0) def is_empty(self) -> bool: """Return True if the queue is empty, return False otherwise.""" return len(self._data) == 0 def __str__(self) -> str: """Return content of the queue as a string (for use with print).""" data_str = [str(item) for item in self._data] return "QUEUE { " + ", ".join(data_str) + " }" class Stack: """ Class implementing STACK ADT. Supported methods are: push, pop, top, is_empty DO NOT CHANGE THIS CLASS IN ANY WAY YOU ARE ALLOWED TO CREATE AND USE OBJECTS OF THIS CLASS IN YOUR SOLUTION """ def __init__(self): """Initialize empty stack based on Python list.""" self._data = [] def push(self, value: object) -> None: """Add new element on top of the stack.""" self._data.append(value) def pop(self): """Remove element from top of the stack and return its value.""" return self._data.pop() def top(self): """Return value of top element without removing from stack.""" return self._data[-1] def is_empty(self) -> bool: """Return True if the stack is empty, return False otherwise.""" return len(self._data) == 0 def __str__(self) -> str: """Return content of the stack as a string (for use with print).""" data_str = [str(item) for item in self._data] return "STACK: { " + ", ".join(data_str) + " }"