Construct a binary search tree using the following input

$($in the given order$)50,26,72,12,11,94,53,99,67,98,37,80$

$($a$)$ Is the above tree a valid AVL tree?

$($b$)$ Delete the following nodes from the above tree using the AVL

delete $($in the given order$)37,12,80,50,98,11$

Show all you intermediate steps as you are deleting nodes from

the tree including the rotation operations.

$(20$ points$)$ Construct a binary search tree using the following input

$($in the given order$)50,26,72,12,11,94,53,99,67,98,37,80$

$($a$)$ Is the above tree a valid AVL tree?

$($b$)$ Delete the following nodes from the above tree using the AVL

delete $($in the given order$)37,12,80,50,98,11$

Show all you intermediate steps as you are deleting nodes from

the tree including the rotation operations.

$(20$ points$)$ Construct a red black tree using the following input $($in

the given order$)50,26,72,37,28,15,17,24$

Show all your intermediate steps including the recoloring and restruc$-$

turing operations.