a$)$ Label each node for each of these trees with their balance factors. Which of these trees

are not AVL trees? Multiple answers are possible. Explain why.

b$)$ For the trees which are not AVL trees, draw the sequence of rotations needed to balance

them and label the rotation done in each step $($left$,$ right, double$-$rotation$($s$)[$ left$-$right, right$-$left$]).$

What is the worst case search time for an AVL tree? Justify your answer mathematically by

discussing the properties and structure of an AVL tree.