Bit$-$saving

For an AVL tree, decisions need to be made about which rotation to perform based on the balance factor B$($x$).$ This factor is calculated as the difference in heights of the trees; one way would be to store the height in each tree and keep track of it$.$ We want to implement rotateLeft to maintain the balance factor B stored for each tree. These numbers should only take the values $-1,0,1$ when we have a valid AVL tree and thus only take up $2$ bits of memory.

Below is an implementation of rotateLeft without keeping track of B$,$ and we assume that B is a field in T$.$

Find out how to modify the code below to calculate the new B values. Assume that Tree T is a valid AVL tree, but the new tree may not be a valid AVL tree. Describe in which cases the AVL tree remains valid after a left rotation $($hint: divide into cases based on the values of T$.$B and T$.$right.B$)$Tree rotateLeft$($Tree T$)\{$

Tree $x=$ T$.$right;

T$.$right $=x.$ left;

$x*left=T$;

return $x$;

$\}$