Please help in Python 3.Given code for BST.py## Node classclass Node():def __init__(self, val):self.__value = valself.__right = Noneself.__left = Nonedef setLeft(self, n):self.__left = ndef setRight(self, n):self.__right = ndef getLeft(self):return self.__leftdef getRight(self):return self.__rightdef getValue(self):return self.__value# BST classclass BST():def __init__(self):self.__root = Nonedef append(self, val):node = Node(val)if self.__root == None:self.__root = nodereturncurrent = self.__rootwhile True:if val <= current.getValue():if current.getLeft() == None:current.setLeft(node)returnelse:current = current.getLeft()else:if current.getRight() == None:current.setRight(node)returnelse:current = current.getRight()def searchLength(self, val):if self.__root == None:return -1current = self.__rootlength = 0while current != None:if current.getValue() == val:return length + 1elif val < current.getValue():length += 1current = current.getLeft()else:length += 1current = current.getRight()return lengthdef __contains__(self, val):if self.__root == None:return Falsecurrent = self.__rootwhile current != None:if current.getValue() == val:return Trueelif val < current.getValue():current = current.getLeft()else:current = current.getRight()return False Part 3: Comparing Performance of Lists and BSTS as a function of the number of elements.Now time for the main part of your script!We want to see how the number of comparisons change for both a list and BST as the number of elements increases.In the main part of your script do the following:1. Create empty lists to store the results of average number of comparisons for a list and BST2. for n in range(1, 1000, 100)1. Set sumcountlist = 0, sumcountbst = 0 and numruns%3D2. for s in range(1, 5)1. Create a list of length n using your populateList function.2. Create a BST from that list, using your 1listToBST function3. for v in range(n)1. Use your searchLength function to determine how many comparisons to find v in your list. Add this to yoursumcountlist2. Use the searchLength method of the BST class to determine how many comparisons to find v in your BST. Addthis to your sumcountbst3. Update numruns3. Computer the average number of comparisons by dividing sumcountlist and sumcountbst by the total number of timesyou contributed to these sums (numruns) and append these to your lists storing the average number of comparisons.3. Output your results as:Average Search Length for List: Average Search Length for BST: Searching for DataIn this lab we'll compare the time it takes to search for an item in a list vs searching for it in a binary search tree.Part 1: Populating and Searching a ListLet's start off in our main.py file.First import the random module, then implement the following functions:populateList(n, s):This function takes as a parameter a positive integer n, and a positive integer s and returns a list of length ncontaining a shuffling of the numbers 0 to n - 1. Prior to shuffling use random.seed(s) to seed the random number generator.We're doing this so we can have reproducible results. Then use the random.shuffle(lst) to shuffle your list.searchLength(lst, n):This function takes as a parameter a list 1st and a positive integer n, which is the value to be searched.The function returns how many elements of 1st had to be inspected before finding n. If n was not encountered, it will return thelength of 1st.The first two unit tests will test running the functions and obtaining expected results.Part 2: Populating Binary Search Tree from a ListYou have been provided a module called BST. This module contains a modified implementation of a Binary Search Tree (BST class) andassociated Node class.The BST class has the following public methods:(self):Creates an empty binary search tree.value): Creates a Node with the value value and inserts it into the BST.(self, value):Returns True if value is in the BST and False otherwise.• Constructorinitappend(self,_containssearchLength(self, value): returns how many elements had to be inspected before finding value as the data in a node orhitting a leaf node during the search.Add to your main script a function called listToBST(lst) that takes a list 1st, appends its elements to an empty Binary Search Tree inthe order provided (e.g. as encountered in 1st), and returns that Binary Search Tree object.The next set of unit tests will test running this function and obtaining expected result.

As you have posted multiple questions, we will solve the first question for you. The code for part1…

Searching for Data In this lab we'll compare the time it takes to search for an item in a list vs searching for it in a binary search tree. Part 1: Populating and Searching a List Let's start off in our main.py file. First import the random module, then implement the following functions: • populateList(n, s):This function takes as a parameter a positive integer n, and a positive integer s and returns a list of length n containing a shuffling of the numbers 0 to n - 1. Prior to shuffling use random.seed (s) to seed the random number generator. We're doing this so we can have reproducible results. Then use the random.shuffle(1st) to shuffle your list. • searchLength(lst, n):This function takes as a parameter a list 1st and a positive integer n, which is the value to be searched. The function returns how many elements of 1st had to be inspected before finding n. If n was not encountered, it will return the length of 1st. The first two unit tests will test running the functions and obtaining expected results. Part 2: Populating Binary Search Tree from a List You have been provided a module called BST. This module contains a modified implementation of a Binary Search Tree (BST class) and associated Node class. The BST class has the following public methods: • Constructor append (self, value):Creates a Node with the value value and inserts it into the BST. • _contains__(self, value): Returns True if value is in the BST and False otherwise. • searchLength(self, value): returns how many elements had to be inspected before finding value as the data in a node or hitting a leaf node during the search. init_(self): Creates an empty binary search tree. Add to your main script a function called listToBST(lst) that takes a list 1st, appends its elements to an empty Binary Search Tree in the order provided (e.g. as encountered in 1st), and returns that Binary Search Tree object. The next set of unit tests will test running this function and obtaining expected result.