Part A: (30 marks) Question 1 (30 marks) a. The INORDER traversal output of a binary tree is U,N,I,V,E,R,S,I,T,Y and the PREORDER traversal output of the same tree is U,1,1,N,S,R,V,E,T,Y. Construct the tree and determine the output of the POSTORDER traversal output. (5.0 marks) b. One main difference between a binary search tree (BST) and an AVL (Adelson-Velski and Landis) tree is that an AVL tree has a balance condition, that is, for every node in the AVL tree, the height of the left and right subtrees differ by at most 1. Starting with an empty BST and AVL tree, insert elements into the two trees with the following keys: (i) 7, 11, 12, 18, 21 (ii) 20, 30, 80, 40, 10, 60, 50, 70 (10.0 marks) C. Based on what you have done for Question 1b, what is the big-O (worst case) complexity of the total time required to build a binary search tree (BST) consisting of n nodes? Explain your answer. Answer without explanation gains no mark. (Hint. A tricky question. The question asks for worst case complexity. Think properly.) (5.0 marks) d. A list of student's names is maintained in an AVL tree T. Design an algorithm for performing the operation findAll to return all the names in the AVL tree that match the searched name. Note that there is a posibility that same names exist in the tree. In the case that the same name exists, the name is added to the left subtree. (10.0 marks)