Explain an efficient method to find the k-th smallest number in a set of nnumbers (output: one number), without first sorting the n numbers, and...

Explain an efficient method to find the k-th smallest number in a set of nnumbers (output: one number), without first sorting the n numbers, and discussits complexity in terms of n and k. [4 marks](b) Explain an efficient method to find the k smallest numbers in a set of n numbers(output: k numbers), without first sorting the n numbers, and discuss itscomplexity in terms of n and k. How much extra work is needed comparedto (a)? [4 marks](c) Draw four distinct binary search trees (BSTs) for the following set of keys:{1, 2, 3, 4}. [2 marks](d) Let a height-balanced BST (hBST) be a BST with the additional defininginvariant that each node is the parent of subtrees whose heights differ by atmost 1. Give an efficient procedure to insert into an hBST and prove that thedefining invariant is preserved. [10 marks