1. Suppose you wanted to insert the numbers 1,2,3,4,5,6,7,8,and 9 into a AVL binary search tree-

a) In what order could you insert the numbers to produce no tree rotation?

b) In what order could you insert them to have a maximal number of tree rotations (keep in mind that some insertions can cause 2 rotations if you have opposite -sign balance factors).

2. A binary tree(Note: this is not a binary search tree) has the following preorder and in-order traversals:

Preorder: C,T,S,O,B,A,B,T,I

In-order: B,O,S,B,A,T,T,C,I

Find the Postorder traversal.