<jupyter_start><jupyter_text>Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel$\rightarrow$Restart) and then **run all cells** (in the menubar, select Cell$\rightarrow$Run All).Note that this Pre-class Work is estimated to take **37 minutes**.Make sure you fill in any place that says `YOUR CODE HERE` or "YOUR ANSWER HERE", as well as your name and collaborators below:<jupyter_code>NAME = "<NAME>"
COLLABORATORS = ""<jupyter_output><empty_output><jupyter_text>---  CS110 Pre-class Work - Binary Search Trees (BSTs) Question 1. (Exercise 12.2-1, Cormen et al.) [time estimate: 5 minutes]Suppose that we have numbers between 1 and 1000 in a binary search tree, and we want to search for the number 363. Which of the following sequences could not be the sequence of nodes examined?a. 2, 252, 401, 398, 330, 344, 397, 363.b. 924, 220, 911, 244, 898, 258, 362, 363.c. 925, 202, 911, 240, 912, 245, 363.d. 2, 399, 387, 219, 266, 382, 381, 278, 363.e. 935, 278, 347, 621, 299, 392, 358, 363. If the nodes I examine are in the order that I go through is listed above, I can not observe c and e. C can not be observed as we cannot encounter 912 after 911, and E cannot be observed as we cannot encounter 299 after 347.   Question 2. Comparing complexities [time estimate: 7 minutes]Complete the following table with the average vs worst case complexities for the data structures in each row.You should copy the following table and paste and edit it in the cell below. Operations | BST | Hash table using open addressing | Min heap--- | --- | --- | ---Search |  |  |Find max |  |  |Find min |  |  |Max extraction  |  |  |Min extraction |  |  |Find successor |  |  |Find predecessor |  |  |Insert |  |  |Delete |  |  | Operations | BST | Hash table using open addressing | Min heap--- | --- | --- | ---Search |  logn or n |  | nFind max |  " |  |nFind min |  " |  |1Max extraction  | " |  |nMin extraction |  "|  |lognFind successor |  "|  |nFind predecessor | " |  |nInsert | " |  |lognDelete | " |  |logn  Question 3. Programming a recursive BST [time estimate: 12 minutes]Given the code in the cell below, write python code for the corresponding functions:* function `search(self, value)`: searches a *non-empty* BST rooted at the node for a node with `data=value`, returns the node if found, None otherwise* function `delete(self, value)`: if a node with data = value is present in the tree rooted at Node, deletes that node and returns the root.* function `inorder(self)`: returns a list of all data in the tree rooted at root produced using an in order traversal. When correctly implemented on a BST, the produced list will be sorted in ascending order.You may find it useful to define additional helper functions.<jupyter_code>## Binary Search Tree
##
class Node:
    def __init__(self, val):
        self.l_child = None
        self.r_child = None
        self.parent = None
        self.data = val

    def insert(self, node):
        """inserts a node into a *non-empty* tree rooted at the node, returns
        the root"""
        if self.data > node:
            if self.l_child == None:
                self.l_child = Node(node)
                self.l_child.parent = self
            else:
                self.l_child.insert(node)
        else:
            if self.r_child == None:
                self.r_child = Node(node)
                self.r_child.parent = self
            else:
                self.r_child.insert(node)
        return self
    
    def minimum(self):
        node = self
        while node.l_child != None:
            node = node.l_child
        return node

    def search_data(self, value):
        """searches a *non-empty* tree rooted at the node for a node with
        data = value, returns the value if found, None otherwise"""
        node = self.search(value)
        if node:
            return node.data
        else:
            return node
        
    def to_string(self): 
        print('self.data', self.data)
        root=self
        if not root: 
            return 'Nil'
        else: 
            r = root.r_child.to_string() if root.r_child else 'Nil'
            l = root.l_child.to_string() if root.l_child else 'Nil'
        return 'Node(' + str(root.data) + ' L: ' + l + ' R: ' + r + ')'
    
    def search(self, value):
        if self.data > value:
            return self.l_child.search(value)
        elif self.data == value:
            return self
        else:
            return self.r_child.search(value)
        
    def delete(self, value):
        if self.data == value:
            self.l_child = None
            self.r_child = None
            return self.parent
        elif self.data > value:
            return self.l_child.delete(value)
        else :
            return self.r_child.delete(value)
        
    def inorder(self):
        printout = []
        while self.parent.value != None:
            printout.append(self.l_child.value)
            printout.append(self.value)
            printout.append(self.r_child.value)
            return self.parent.inorder()
BST = Node(10)
for i in [1,2,3,11,12,13]:
    BST.insert(i)
BST.inorder()<jupyter_output><empty_output><jupyter_text>Question 4. Validating the BST python code [time estimate: 13 minutes] Question 4a [time estimate: 3 minutes]It is good practice to make the necessary tests in your code to ensure it produces the intended outputs. In the cells below, implement slow, but simple:* inserts,* searches,* deletes.<jupyter_code>def list_insert(lst, value):
    """inserts value into lst in sorted order"""
    for i in lst:
        if self.search(i) == None:
            node = Node(i)
            self.insert(node)
    

def list_delete(lst, value):
    """ deletes first instance of value from lst if it present"""
    for i in lst:
        if self.search(i) == i:
            self.delete(i)
def list_search(lst, value): 
    """ searches lst for value and returns value if present, None if it is not present"""
    for i in lst:
        self.search(i)<jupyter_output><empty_output><jupyter_text>Question 4b [time estimate: 10 minutes]Run the testing code provided in the cell below to generate a sequence of random inserts, followed by a sequence of random deletes, and finally followed by a sequence of random searches. Apply this sequence to both your BST implementation and the sorted list implementation. Do the final results both match? Does this mean your code is free of bugs? Provide your answer to these questions in the cell below the Python-code cell.<jupyter_code>bst = None # bst is a misnormer, this variable contains the Node that is the root of the BST of interest
lst = []

my_Nodes = [2, 3, 5, 1]
for x in [Node(_) for _ in my_Nodes]:
    print("###################")
    print('Inserting the following node: ', x.data)
    if not bst:
        bst = x
    else:
        bst = bst.insert(x)
    print(bst.to_string())
# YOUR CODE HERE
raise NotImplementedError()<jupyter_output><empty_output><jupyter_text>It seems okay as insertion was done with all four elements without red errors popping up. Also the inputs were well landed in place which is a form of below.<jupyter_code>from IPython.display import Image
Image(filename="C:/Users/green/Desktop/2351.jpg")<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09612762476138532, 'fraction_numerical': 0.024543223343332424, 'mean_word_length': 2.7082912032355915, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 25, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '480761', 'license': 'MIT', 'n_tokens_mistral': 2318, 'n_tokens_neox': 2097, 'n_words': 872, 'path': 'CS110 PCW 16 Binary Search Trees (BSTs).ipynb', 'repo_name': 'Jeongwoo-KGI/sides-and-school', 'size': '7342'}