In a binary tree (BT), a path between the root and a leaf is the number of arcs joining the root to the leaf. The BT $$\texttt{height}$$ is the length of the longest path between the root and each of the leaves.

• Write a function $$\texttt{int height(BT T)}$$ that returns the height of T.
• The search algorithm in a $$\texttt{BST}$$ is proportional to its height. In order to improve the search performance, we consider the class of balanced $$\texttt{BST}$$. A $$\texttt{BST T}$$ is balanced if $$\texttt{T}$$ is empty or if for each node, the difference between the heights of the left and right subtrees is $$<$$ 2.
  Write a function $$\texttt{int dif_LR(BT T)}$$ that returns the difference between left and right subtree height of a given $$\texttt{BT T}$$.
• Write a function $$\texttt{int balanced(BT T)}$$ that returns 1 if $$\texttt{T}$$ is balanced and 0 otherwise.
• In order to ensure the balance of a $$\texttt{BST}$$, we suggest to transform it using the following rotations:
  • Left Rotation: a left rotation around the node B consists in getting down B and getting up its right child D without invalidating elements order (see figure below).
  • Right Rotation: the reverse of the left rotation.
    
  • Left-Right Rotation on T: it consists in a left rotation on T left subtree followed by a right rotation on T.
  • Right-Left Rotation on T: it consists in a right rotation on T right subtree followed by a left rotation on T.
    
  Write a function $$\texttt{left_rotation}$$ that rotates left a given $$\texttt{BST}$$. You must only manipulate pointers; no memory allocation or release is allowed.
• Write a function $$\texttt{left_right_rotation}$$ that rotates left-right a given $$\texttt{BST}$$.
• The insertion of an element into a balanced $$\texttt{BT}$$ is as follows: the element is added as when inserting into a $$\texttt{BST}$$ then:
  • If the left balance is lost then a left-right rotation is done if the left child lean to the right, otherwise a simple right rotation is done.
  • If the right balance is lost then a right-left rotation is done if the right child lean to the left, otherwise a simple left rotation is done.
  Assuming that a binary tree $$\texttt{T}$$ is said to be left-leaning if $$\textbf{dif_LR(T)>0}$$, and suppose having the functions: $$\texttt{lean_L}$$, $$\texttt{lean_R}$$, $$\texttt{left_rotation}$$, $$\texttt{left_right_rotation}$$, $$\texttt{right_rotation}$$, and $$\texttt{right_left_rotation}$$, write a function to insert an element into a balanced $$\texttt{BST}$$ that implements the described insertion procedure.

int height(Btree B) 
{
	if (isEmpty_Btree(B) || B->left ==NULL && B->right ==NULL) 
		return 0;	
	return 1 + max(height(B->left),height(B->right));		
}


int dif_LR(Btree B)
{
	return (height(B->left) - height(B->right));
} 


int balanced(Btree B) 
{
	return ((B==NULL) || (abs(dif_LR(B))<2 && balanced(B->left) && balanced(B->right)));
}


void left_rotation(Btree *B) 
{
	Btree T1; 
	if (*B == NULL) return ; 

	T1=(*B)->right; 
	(*B)->right = T1->left; 
	T1->left = *B;
	*B = T1 ; // new root
} 

void right_rotation(Btree *B) 
{
	Btree T1; 
	if (*B == NULL) return ; 

	T1=(*B)->left; 
	(*B)->left = T1->right; 
	T1->right = *B;
	*B = T1 ; // new root
} 

void left_right_rotation(Btree *B)
{   
	if (*B == NULL || (*B)->left == NULL) return; 	
	left_rotation(&((*B)->left)); 
	right_rotation(B); 
}


void right_left_rotation(Btree *B)
{   
	if (*B == NULL || (*B)->right == NULL) return; 	
	right_rotation(&((*B)->right)); 
	left_rotation(B); 
}
  

int Insert_BST(element1 X, Btree *T )
{ 	
	if( isEmpty_Btree(*T)) 
	{ // Create and return a one-node tree 
		*T = (Btree) malloc(sizeof(struct node));
		(*T)->data = X;
		(*T)->left = (*T)->right =  NULL; 
		return 1 ; 
	}
	else 
		if( X == (*T)->data)
			return 0;
	if( X < (*T)->data)
		return Insert_BST( X, &((*T)->left) );
	return Insert_BST( X, &((*T)->right) );
}

int left_lean(Btree B)
{ 
	return (dif_LR(B) > 0); 
} 

int right_lean(Btree B)
{ 
	return (dif_LR(B) < 0); 
} 


int Insert_Balanced(element1 X, Btree *T )
{
	if (!Insert_BST(X,T)) 
		return 0; //nothing to insert	
	if (X < (*T)->data) //element inserted on the left	
		if (right_lean((*T)->left)) 
			left_right_rotation(T); 	
		else 
			right_rotation(T);
	else //element inserted on the right	
		if (left_lean((*T)->right)) 
			right_left_rotation(T); 	
		else left_rotation(T);

	return 1;
}