University of Engineering and Technology

Department of Electrical Engineering

Problem Set 3 Points: 20 Date: February 24, 2022 Due: March 4, 2022

Lab
Question 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 points
This question concerns Binary Search Trees. The basic tree has been implemented for you.
(a) (1 point) Write a recursive function tree min that finds the minimum value in a binary
search tree (BST).
(b) (1 point) Implement the tree successor function that given a value in a tree, it finds its
successor value. If the value is not in the tree the behaviour is undefined.
(c) (1 point) Using the tree min and tree successor functions, write a function inorder walk
that performs the inorder tree walk on a BST.
(d) (1 point) Write a recursive function check BST that decides (returns True or False) whether
a binary tree is a BST.

Question 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 points
An implementation of the heap data structure has been given to you. This question relates to
that implementation:
(a) (2 points) In the initialization of MaxHeap there is a line [Link][0] = [Link].
Remove this line of code. Modify the rest of the class so that without using [Link],
your implementation of MaxHeap works correctly.
(b) (4 points) Start with a fresh copy of the class MaxHeap (without your modification of the
previous exercise). Now if you compare the code given with the pseudocode given in the
textbook there are some differences. Your task is to remove those differences. In particular
modify the given code so that (a)maxHeapify has the same algorithm as the one described
in the textbook and (b) the algorithm for construction of max-heap is the same as the one
in the book. Hence, after your modification the following code should construct a max-heap
>>> a = MaxHeap([15, 5, 3, 17, 10, 84, 19, 6, 22, 9])

Theory

Question 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 points
Prove the following:
(a) A heap with n nodes has a height of blg nc
(b) In our array representation for storing an n-element heap, the leaves of the node are indexed
by b n2 c + 1, · · · , n.
n
(c) Show that there are at most d 2h+1 e nodes of height h in any n-element heap.
(d) Calculate
∞
X h
2h
h=0
.
Question 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 points
Solve the following recurrences using the method described.
(a) T (n) = T (k)+T (n−k −1)+d. Prove that T (n) = O(n). Hint: Find a c such that T (n) ≤ cn
for all n.
(b) T (n) = 2T (n/4) + 1. Use the master theorem.
(c) T (n) = 2T (n/4) + n2 . Use the master theorem.
(d) T (n) = T (n − 1) + T (n/2) + n. Use the tree method to find an upper bound. Verify your
answer by substituting the answer into the recursion.
(e) T (n) = 4T (n/2) + n2 lg n. Any method.
√
(f) T (n) = T ( n) + 1. Any method.

Question 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 points
Prove that the tree successor procedure discussed in the class (code is given on page 292 of
textbook) is correct.

Question 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 points
Prove that the recursive tree min function that you wrote in the laboratory part is correct.
What is the worst-case running time of this function? What is the best-case running time of this
function?

Question 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 points
Calculate a tight asymptotic bound on the function inorder walk that you wrote in the laboratory
part of this problem set.

Question 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 points
We can sort a set of numbers by first building a binary search tree by repeated insertions and then
printing the numbers by an inorder tree walk. What are the best-case and worst-case running
times of this sorting algorithm?

Question 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 points
Let T be a binary search tree. Does deleting node x and then node y of T lead to a different tree
as compared to first deleting node y and then node x? Argue that your claim is correct.

Page 2