Question 3 [55 minutes] This question is about binary search trees a. Briefly describe an implementation of binary search trees and write a C function bst.search() which will search a binary search tree for a particular key. If the key is found it should return the subtree rooted at that node (eg, a pointer to the node); otherwise it should return the empty tree. You may assume keys are integers. b. It would be advantageous to support trees with different types of keys. Describe how bst.search) could be generalized to do so in C. c. Some tree insertion code will always insert a node with a key equal to the root into the right sub-tree. Briefly explain why keys equal to the root may appear in the left or right sub-trees in balanced search trees d. Describe an algorithm which will find all occurrences of a particular key in a (pos- sibly balanced) binary search tree. For each occurrence it should call the function foundone () with the pointer to the node. e. Write a C function bst search all() which implements the algorithm above. You f. Describe an algorithm which will check if a binary search tree contains duplicate g. Write a C function has.dup.keys) which implements the algorithm above. You may assume keys are integers. keys. may assume keys are integers. Question 3 [55 minutes] This question is about binary search trees a. Briefly describe an implementation of binary search trees and write a C function bst.search() which will search a binary search tree for a particular key. If the key is found it should return the subtree rooted at that node (eg, a pointer to the node); otherwise it should return the empty tree. You may assume keys are integers. b. It would be advantageous to support trees with different types of keys. Describe how bst.search) could be generalized to do so in C. c. Some tree insertion code will always insert a node with a key equal to the root into the right sub-tree. Briefly explain why keys equal to the root may appear in the left or right sub-trees in balanced search trees d. Describe an algorithm which will find all occurrences of a particular key in a (pos- sibly balanced) binary search tree. For each occurrence it should call the function foundone () with the pointer to the node. e. Write a C function bst search all() which implements the algorithm above. You f. Describe an algorithm which will check if a binary search tree contains duplicate g. Write a C function has.dup.keys) which implements the algorithm above. You may assume keys are integers. keys. may assume keys are integers