Structures and Algorithms Homework 8 Solution

Question 1:




Given the following binary search tree bst:







9




13



3 11 15




5



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:




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.

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 non-negative integer k.




For example, the call create_complete_bst(7) following structure (with the values 1, 2, 3, 4, 5, 6, 7 order):




should create a tree of the inside its nodes in a valid









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)

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:




9




13



3 11 15




5



Notes:




The runtime of this function should be linear.



Assume that prefix_lst contains integers.



Assume that there are no duplicate values in prefix_lst.



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:







9




20



4 17 25




6



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).

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:




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 Θ(ℎ ℎ ).



You should raise an IndexError exception in case i is out of range.



Hints:




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.



You may want to define additional helper methods.