Sally has sent you a record of the order in which she INSERT$-$ed friends into her BST$.($Note that in this case, Hananah

starts out being the best friend, as she is added first. The best friend will not necessarily be the same person throughout

the lifetime of the BST$.)$

Name Birthday

Hannah $8$ August

Georgie $7$ July

Dani $4$ April

Callum $3$ March

Feroz $6$ June

Abby $1$ January

Ben $2$ February

Ethan $5$ May

Draw a diagram of Sally's current BST and compile a list of the sequence of ROTATE emails Sally would need to

send in order to reorganise the BST so that subsequent SEARCH times are minimised. You don$’$t need to include the

full text of the emails, but your list should indicate who to send the email to$,$ which friend needs to be changed, and

which form of ROTATE to use. Include intermediate diagrams showing the effect of each rotation on the BST$.$ Note

that it may be necessary for Sally herself to change her best friend using a ROTATE.

Further Explanation: These operations correspond to the standard rotate operations that are defined for a binary

search tree. For this question and also the next one, you are asked to create diagrams to illustrate what happens as the

tree is rotated. These diagrams do not need to be created with software; images$/$photos of neat hand$-$drawn diagrams

are fine.

You should draw the initial state of the BST after all of the friends have been added, in the order shown above. Next,

you should provide a diagram to show the effect of every rotation applied in order to balance the tree. For this question,

you should finish with a balanced tree that provides optimal efficiency for inserting and searching $($i$.$e$.$ not using the

AVL definition of a balanced tree, which will be used in question $3).$