Consider the basic definition of a Binary Search Tree $($BST$),$ where:

a BST $T$ is an object that has a single attribute: $T.$ root which is a pointer to its root node.

each node $x$ of the tree has $4$ attributes:

$x.$ key: identifier of the object stored in the node.

$x.$parent: pointer to the parent node; NIL for T$.$ root.

$x.$ left: pointer to the left child; eventually NIL.

$x.$right: pointer to the right child; eventually NIL.

the keys of the nodes of left subtree of a node $x$ are all smaller the key of $x.$

the keys of the nodes of the right subtree of a node $x$ are greater or equal to the key of $x.$

$1-$ Write a divide and conquer algorithm to compute and return the size of subtree rooted at a

given node $x$ of a BST$.$ The size of the subtree rooted at $x$ is the number of nodes in that

subtree, including $x.$ For instance,

the size of the tree rooted at a leaf node is $1$

the size of the subtree rooted at T$.$ root is the total number of nodes in the tree T$.$

What is the running time of this algorithm? Explain.

$2-$ Assume we want to augment the initial definition of the BST$,$ by an additional attribute $x.$ size

per node that stores the size of the subtree rooted at it$.$

Provide the modified Augmented$-$BST$-$insert $(T,z)$ pseudocode of the insertion operation that

maintains this new attribute and has the same asymptotic running time as the original BST$-$

insert$()$ i$.$e$.O(h),$ where $h$ is the height of the tree.

$3-$ Write the pseudocode of Augmented$-$BST$-$select $(T,k)$ operation, which returns the key in a BST

tree with a given order statistic $k$ i$.$e$.$ returns the $k^{th}$ smallest element of the tree. Augmented$-$

$BST-$select $(T,k)$ must have a $O(h)$ running time.

$4-$ If we want to achieve $O(logn)$ selection operation, we need the BST to be balanced $($e$.$g$.$ AVL$).$

So$,$ at insertion $($and deletion$)$ we need to eventually perform rotations to reestablish the tree

balance. The modified Augmented$-$BST$-$insert $(T,z)$ should update the size attribute for the

nodes affected by the basic BST insertion; however the subsequent eventual rotations will

render it incorrect for a few. Provide a modified Augmented$-$LEFT$-$ROTATE$()$ pseudocode that

corrects$/$fixes the size attributes disrupted by the rotation.