4. This question has two parts: a) Draw the BSTs that result from the following two different insertion sequences of the same set of elements: Insertion sequence: 871 6 2 3 54 Insertion sequence: 57 3 2 8 6 4 1 For both cases, start with an empty tree. Just showing the final tree in your answer is sufficient. Alternatively, if you want to show the BST after every insertion, that is fine too. b) Briefly state what is so markedly different between the shapes of the two resulting BSTs. 5. starting with an empty tree Te, show the set of BSTs Te=9T1=9T2 T6 resulting from performing the following sequence of operations (in that order) Insert(5) Insert(10), Insert (2), Insert(7), Insert (6), Remove(5) 6. This question has two parts. a) Starting with an empty tree Te, show the set of AVL trees Te T2 resulting from performing the following sequence of operations (in that order): Insert(7), Insert(5) Insert (2), Insert (4) Insert(3), Insert(1). If at any step you need to rebalance the tree using rotation, then clearly identify: (i) the node that has the imbalance (i.e., violation, and (ii) the corresponding rotation "case" that applies there (i.e., case 1 or 2 or 3 or 4 b) Answer the same question as in part (a) but with this insertion sequence instead: Insert (2) Insert(1), Insert (4) Insert(5), Insert (9), Insert() Insert(6), Insert(7)