// Fragment of the code
// Note: this a bit different implementation than presented on the slide!
//       it takes care of changing the root, it it gets changed by the operation


TreeNode<T> leftRotate(TreeNode<T> root,TreeNode<T> x)
// returns a new root
// Pre: rigth child of x is a proper node (with value)
{
  TreeNode<T> z = x.getRight();

  x.setRight(z.getLeft());
  // Set parent reference
  if (z.getLeft() != null)
    z.getLeft().setParent(x);
 
  z.setLeft(x); //move x down 

  z.setParent(x.getParent()); 
  // Set parent reference of x
  if (x.getParent() != null) //x is not the root 
    if (x == x.getParent().getLeft()) //left child 
      x.getParent().setLeft(z);
    else
      x.getParent().setRight(z);
  else
		root=z;

  x.setParent(z);
	return root;
}