2 8 2. This question is based on a question from Spring 2017 Exam 1. The following code fragment defines a structure for storing a binary tree and a function for re-constructing a binary search tree from an array of integers. The integers in the array are ordered according to the postorder traversal of the original binary search tree. We also assume that all integers are distinct. Also assume that all malloc calls are successful. 1 typedef struct _tnode { int value; 3 struct tnode *left, *right; 4) tnode; 5 6 toode *build_bst_from_postorder (int *array, int lb, int ub) 7 { if (lb > ub) { 9 return NULL; 10 } 11 toode *node = malloc(sizeof (*node)); 12 node-> value = array[ub]; 13 14 // find the left subtree and the right subtree of node in the array 15 // assume that all integers in left subtree value 16 int partition_idx lb; 17 while ((partition_idx left = build_bst_from_postorder (array, lb, partition_idx-1); 21 node->right = build_bst_from_postorder (array, partition_idx, ub-1); 22 return node; 23 ) (a) Instead of using a linear search to search for partition_idx, replace lines 16-19 with an iterative binary search to determine partition_idx. Write down the pseudo-code for a suitable replacement. (b) Consider the replacement that you have made in (a). Let n be the number of integers in the array passed to the function build.bst_from_postorder. ) What is the worst-case space complexity for the re-construction of the entire binary search tree in terms of n using the big-o notation? (ii) What is the best-case space complexity? Justify your answers. Your answers should not include the space required for the input array and the re-constructed binary search tree. (c) Consider the replacement that you have made in (a). Let n be the number of integers in the array passed to the function build_bst_from_postorder. (1) What is the worst-case time complexity for the re-construction of the entire binary search tree in terms of n using the big-O notation? (ii) What is the best-case time complexity? It is important to take into account the time complexity in executing lines 16-19 (the replaced version in (a) of the function. Justify your answers