DATA STRUCTURES

Question 3 (10 marks) a) The INORDER traversal output of a binary tree is S,T,R,A,W,B,E,R,R,Y and the PREORDER traversal output of the same tree is S,W,T,A,R,R,E,B,Y,R. Construct the tree and determine the output of the POSTORDER traversal output. (2.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 the following keys into the two trees (BST as well as AVL trees): 19,62,23,57,18,12,36,82,11,74 If a key is already existed, insert the new key to the right sub-tree. (4.0 marks) c) Based on what you have done for Question 3b, 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.) (2.0 marks) d) Similarly, from what you have done for Question 3c, what is the big-o (worst case) complexity of the total time required to build an AVL tree consisting of n nodes? Explain your answer. Answer without explanation gains no mark. (Hint. The question asks for worst case complexity.) (2.0 marks)