(Solved): These codes need to be used as a reference to receive a score so please use them     ...

These codes need to be used as a reference to receive a score so please use them

 

 

Please code in Python

BinarySearchTreeMap. Question 2: a. Implement the following function: def create_chain_bst(n) This function gets a positive integer \( \mathrm{n} \), and returns a binary search tree with \( \mathrm{n} \) nodes containing the keys \( 1,2,3, \ldots, n \). The structure of the tree should be one long chain of nodes leaning to the right. For example, the call create_chain_bst (4) should create a tree of the following structure (with the values 1, 2, 3, 4 inside its nodes in a valid order): Implementation requirement: In order to create the desired tree, your function has to construct an empty binary search tree, and can then only make repeated calls to the insert method, to add entries to this tree. b. In this section, you will show an implementation of the following function: def create_complete_bst \( (n) \) create_complete_bst gets a positive integer \( \mathrm{n} \), where \( \mathrm{n} \) is of the form \( n=2^{k}-1 \) for some non-negative integer \( k \). When called it returns a binary search tree with n nodes, containing the keys \( 1,2,3, \ldots, n \), structured as a complete binary tree. Note: The number of nodes in a complete binary tree is \( 2^{k}-1 \), for some nonnegative integer \( k \). For example, the call create_complete_bst (7) should create a tree of the following structure (with the values \( 1,2,3,4,5,6,7 \) inside its nodes in a valid order): You are given the implementation of create_complete_bst: def create_complete_bst \( (\mathrm{n}) \) : bst \( = \) BinarysearchTreeMap () add_items (bst, 1, n) return bst You should implement the function: def add_items (bst, low, high) This function is given a binary search tree bst, and two positive integers low and high (low \( \leq \) high). When called, it adds all the integers in the range low ... high into bst. Note: Assume that when the function is called, none of the integers in the range low ... high are already in bst. Hints: - Before coding, try to draw the binary search trees (structure and entries) that create_complete_bst \( (n) \) creates for \( n=7 \) and \( n=15 \). - It would be easier to define add_items recursively. c. Analyze the runtime of the functions you implemented in sections (a) and (b)