Complete the Python program which implements a BST class by completing the instructions in the unfinished functions, which are contains(), inorder_traversal(), find_min(), find_max(), is_empty(), make_empty()

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

#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 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) + " }"