struct 3. This question is based on a question from Spring 2019 Exam 2. The following code fragment defines a structure for storing a binary tree and a function for re-constructing a binary search tree (BST) from an array of integers. The integers in the array are ordered according to the preorder traversal of the original BST. The array is called preorder in the function. Assume that all malloc calls are successful typedef struct _Tnode { int key; struct _Tnode *left; Tnode *right; } Tnode; Tnode *Reconstruct_BST (int *index, int *preorder, int size, int ub) { if (*index >= size) return NULL; if (preorder [index] > ub) return NULL; Tnode *node = malloc(sizeof(node)); node->key = preorder [*index); *index += 1; node->left = Reconstruct_BST (index, preorder, size, node ->key); node->right Reconstruct_EST (index, preorder, size, ub); return node; ) (a) The following statements are in the main function. int preorder [] = {16, 12, 10, 14, 20, 18}; int index = 0; // initial position in preorder array int size = sizeof(preorder) /sizeof(preorder [0]); // array size Toode *root = Reconstruct_BST(&index, preorder, size, INT_MAX); Draw the re-constructed BST. Note that INT_MAX is the largest int possible. You may treat it as oo (b) Draw the computation tree that corresponds to the recursive calls of the function Reconstruct_BST in 3(a). The node that corresponds to the first call is shown below. The two terms in the node correspond to +index and ub, where index and ub are parameters passed to the function. You computation tree must show=index and ub in each node. index, ub INT_MAX (e) Let n be the number of integers in the preorder array passed to Reconstruct_BST. C) What is the worst-case space complexity for the re-construction of the entire BST in terms of n using the big-O notation? m) 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 BST. (d) Let n be the number of integers in the preorder array passed to Reconstruct_BST.) What is the worst-case time complexity for the re-construction of the entire BST in terms of n using the big-O notation? c) What is the best-case time complexity? Justify your answers