Question $2$:

a$.$ Implement the following function:

def create$\_$chain$\_$bst$($n$)$

This function gets a positive integer n$,$ and returns a binary search tree with n

nodes containing the keys $1,2,3,...,$ 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$)$:

$3$

$3$

$3$

Implementation requirement: In order to create the desired tree, your

$3$

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 n$,$ where 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,...,$ n$,$ structured as a complete binary tree.

Note: The number of nodes in a complete binary tree is $2$k

$-1,$ for some non$-$

negative 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$)$:

$3$

$33$

$33$

$3$

You are given the implementation of create$\_$complete$\_$bst:

def create$\_$complete$\_$bst$($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 $$ 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:

c$.$ 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.

Analyze the runtime of the functions you implemented in sections $($a$)$ and $($b$)$