Q$4.($a$)$ Draw the Binary Search Tree $($BST$)$ if the following values are inserted into a

tree from left to right one at a time. The tree is empty before the first value is

inserted.

$9,5,13,2,3,11,16,15,88$

$($b$)$ The following questions $($b$($i$)$ and b$($ii$))$ are based on the Binary Search Tree

$($BST$)$ drawn in Q$4($a$).$

$($i$)$ Redraw the tree after node $9$ is deleted.

$($ii$)$ State whether the Binary Search Tree in Q$4($a$)($before deletion$)$ is an

AVL tree? If not, specify which node is not balanced and identify the

unbalance pattern $($eg$.$ LL$,$ LR$,$ LB$,$ RR$,$ RB$,$ RL$).$ Draw the tree after

the balancing.

$($c$)$ Assume that we have numbers between $1$ and $100$ in a Binary Search Tree

$($BST$)$ and want to search for the number $50.$ State whether the examination of

the following sequences for the nodes is valid or not in order to find $50$ and

justify your answer.

$($i$)55,56,57,58,59$

$($ii$)55,43,47,49,48$

$($iii$)100,99,98,50,49$

$($d$)$ Write a recursive function int TreeHeight$($BTNode $*$nodePtr$)$ to return the

height of a Binary Search Tree $($BST$).$Help