Answer only $4$ questions out of $5.$ You are not allowed to answer ALL questions. Question $1$: $(25$ points$)$ Heap Sort

Sort the following list using Heap Sort

$\backslash$table$[[54,79,70,11,7]]$

Hint: you must show the steps in detail exactly as it's explained in the class. You must show the insertion of each element in the $($array and tree$)$ while you preserve the property of max heap. Property of max heap: the root is the largest than its children. Then, delete all the elements and store them in another array and print that array. That array should have sorted values. In the max heap, only the root is deleted.

Question $2$: $(25$ points$)$ Insert the following keys into AVL tree: $20,50,10,7,3,100,150,125,130$ Hint: you must preserve the property of AVL after you insert each element. The property of AVL is a balanced binary tree such that each node has a balance factor in the range of $0,1,-1.$ You must show the balanced factor for each node after you insert a new key. You also must show if the tree is balanced or unbalanced. If it's unbalanced, show the type of unbalanced case and how you fix it$.$

Question $3$: $(25$ points$)$ Binary Search Tree $($BST$)$

Given the below binary search tree, answer A$-$C

A$.(9$ points$)$ Traverse the tree usiriy inorder, preorder, and postorder

Hint: $($ inorder: left root right, preorder: root left right, postorder: left right root

B$.(8$ points$)$ Write the pseudo code to delete $6$ then draw the tree.

C$.(8$ points$)$ Write the pseudo code to delete $9$ then draw the treE