Q3. [30 marks] Answer the following questions about Trees. - (i) [7 marks] Suppose we have a binary tree T1. The inorder traversal sequence and postorder traversal sequence of T1 are given below. Please draw the tree out and also give the preorder traversal sequence of T1. * Inorder traversal sequence of T1:20,33,7,12,19,47,27 * Postorder traversal sequence of T1:20,7,33,19,27,47,12 - (ii). [8 marks] Given a binary tree T2 as shown in Fig. 1, is T2 a max heap? Justify your answer. Next, write down the array representation of the binary tree T2. Please fill the values in the array as shown below. - (iii). [15 marks] Design an algorithm in pseudo-code to count the sum of non-leaf nodes in a binary tree. Your algorithm should use the following Binary Tree ADT operations. For example, the sum of all non-leaf nodes of the binary tree T2 in Fig. 1 is 65+57+41+46=209 Binary Tree ADT * Create(bintree): Create an empty binary tree. * Boolean IsEmpty(bintree): If bintree is empty return TRUE else FALSE. * MakeBT (bintree1, element,bintree2): Return a binary tree whose left subtree is bintree 1 and right subtree is bintree2, and whose root node contains the data element. * Lchild(bintree): If bintree is empty return error else return the left subtree of bintree. * Rchild(bintree): If bintree is empty return error else return the right subtree of bintree. * Data(bintree): If bintree is empty return error else return the element data stored in the root node of bintree