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 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 nodes?

Explain your answer. Answer without explanation gains no mark. (Hint. The question

asks for worst case complexity.)

(2.0 marks)