a. [10 marks] Draw the structure of an AVL tree of height 4 (12 nodes in total), such that for every non-leaf node in the tree the height of the right subtree is exactly 1 plus the height of the left subtree. Note: there is no need to put numbers in the nodes; just draw the structure. b. [5 marks] When we insert a new node an AVL tree we need at most one fix to restore the balance factor. Where each fix consists of 1 or 2 rotations (discussed in the slides). In fact, the violation of the AVL property happens in one subtree and once we fix that we are done. However, when we delete nodes from an AVL tree we may need to repeatedly fix violations all the way up to the root, as fixing each violation results in another violation at a subtree on an upper level. In your drawing from part (a) circle a node that if we delete we need to fix 2 violations to restore the balance of the whole tree