binary search tree question

Please find attached.

Question 1: Binary Search trees
(a) 8 points In class, we defined binary search trees assuming that there were no duplicate keys.
Suppose now that we would like to build a BST in such a way where duplicate keys may exist. To
handle duplicates easily, we augment each node x with an attribute x.count which indicates the number
of occurrences of the key x.key in the tree.
Your job:
⚫ re-write the Tree-Insert(T, z) algorithm from class so that duplicate keys are handled correctly. Is the
runtime the same?
⚫ re-write the BST-delete(T, z) algorithm from practice set 7 so that duplicate keys are handled correctly.
Is the runtime the same?
(b) 12 points Let T be the root node of a BST.
• Write the pseudo-code for a recursive algorithm that returns the total number of nodes in the tree T.
Call your pseudo-code CountNodes(T)
• Write the pseudo-code for a recursive algorithm that fills array A with the elements of T in increasing
order. Call your pseudo-code FillArray(T, A)
• Describe an algorithm that returns the median element of T. Write the pseudo-code and justify why
your algorithm runs in time O(n). You may use the procedures above.