12 points 1. Tree traversals. a. (4pts) Give the sequence of letters from an inorder traversal of this binary tree: agt w Give the sequence of letters from these traversals of the tree below: b. c. (4 pts) a preorder traversal (4 pts) a postorder traversal d ng hj3t 4 points 2. Use the stack-based algorithm for converting a postfix expression into an expression tree for the postfix expression: abs*+ghk+*/* Illustrate each step. 4 points 3. Use your expression tree to find the expression in prefix notation. 10 points 4. Draw an AVL tree for the following values inserted in this order. Illustrate the tree for each rotation that occurs: 83 12 62 55 32 68 74 5. Draw an AVL tree for the following values inserted in this order. Illustrate 9. For the B+-tree where M=3 and L=5 shown below, show how an insert of value 77 is handled. Use the method of splitting the node rather than redistributing between siblings. || 24 || 75 || - | 10 || 16 | || 41 || 50 ||| || 84 || 90 || 16 50 75 84 90 JUN 00 14 20 30 JUN 79 87 93 10 points 10. A B+-tree is to be stored on disk whose block size is 2048 bytes. The data records to be stored are 64 bytes, and their key is 24 bytes. Determine the values for M and L for the B+-tree. Assume pointers are 4 bytes each. 10 points 11. For the problem above, in the worst case, how many levels are needed to store 16,000,000 records