Description
CS-UY 1134 Homework 8
Question 1:
Given the following binary search tree bst:
We are executing the following sequence of operations (one after the other):
bst[6] = None
bst[12] = None
bst[4] = None
bst[14] = None
del bst[7]
del bst[9]
del bst[13]
del bst[1]
del bst[3]
Draw the resulting tree after each one of the operations above.
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):
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.
3
3
3
3
3
9
3
7 3
3
3 3 3
3
1 3
5
11
13
15
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=2k
-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 2k
-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(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:
• 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)
3
3 3
3 3 3
Question 3:
Implement the following function:
def restore_bst(prefix_lst)
The function is given a list prefix_lst, which contains keys, given in an order
that resulted from a prefix traversal of a binary search tree.
When called, it creates and returns the binary search tree that when scanned in
prefix order, it would give prefix_lst.
For example, the call restore_bst([9, 7, 3, 1, 5, 13, 11, 15]),
should create and return the following tree:
Notes:
1. The runtime of this function should be linear.
2. Assume that prefix_lst contains integers.
3. Assume that there are no duplicate values in prefix_lst.
4. You may want to define a helper function.
Question 4:
Implement the following function:
def find_min_abs_difference(bst)
The function is given a binary search tree bst, where all its keys are non-negative
numbers.
When called, it returns the minimum absolute difference between keys of any two
nodes in bst.
For example, if bst is the following tree:
The call find_min_abs_difference(bst) should return 1 (since the absolute
difference between 6 and 7 is 1, and there are no other keys that their absolute
difference is less than 1).
3
9
3
7 3
3
3 3 3
3
1 3
5
11
13
15
3
9
3
7 3
4
3 3 3
3
1 3
6
17
20
25
Implementation requirement:
The runtime of this function should be linear. That
is, if bst contains n nodes, this function should run in Θ(�).
Hint: To meet the runtime requirement, you may want to define an additional,
recursive, helper function, that returns more than one value (multiple return values
would be collected as a tuple).
Question 5:
Modify the implementation of the BinarySearchTreeMap class, so in addition to
all the functionality it already allows, it will also support the following method:
def get_ith_smallest(self, i)
This method should support indexing. That is, when called on a binary search tree, it
will return the i-th smallest key in the tree (for i=1 it should return the smallest
key, for i=2 it should return the second smallest key, etc.).
For example, your implementation should behave as follows:
>>> bst = BinarySearchTreeMap()
>>> bst[7] = None
>>> bst[5] = None
>>> bst[1] = None
>>> bst[14] = None
>>> bst[10] = None
>>> bst[3] = None
>>> bst[9] = None
>>> bst[13] = None
>>> bst.get_ith_smallest(3)
5
>>> bst.get_ith_smallest(6)
10
>>> del bst[14]
>>> del bst[5]
>>> bst.get_ith_smallest(3)
7
>>> bst.get_ith_smallest(6)
13
Implementation requirements:
1. The runtime of the existing operations should remain as before (worst case of
Θ(ℎ���ℎ�)). The runtime of the get_ith_smallest method should also be
worst case of Θ(ℎ���ℎ�).
2. You should raise an IndexError exception in case i is out of range.
Hints:
1. You may want to add attributes to the Node objects to help you search for the ith
smallest element. To keep them updated, it could require you to modify the
insert and delete methods as well.
2. You may want to define additional helper methods.
