import java.util.Stack;

Node balance(Node root, int n)
{
   if ( n <= 1 ) return root;

   // STRIP ITEMS FROM TREE AS LIST

   {//Taking advantage of Java 5.0's generic collections
      Stack <Node> stack = new Stack<Node>();
      Node cur = root, front = null, tail = null;

   // In-order traversal via a stack (after Carrano)

      while ( true )         // Infinite loop exited via break
      {//Carrano code is equivalent in behavior to a "while"
         while ( cur != null )
         {  stack.push ( cur );
            cur = cur.left;
         }
      // What follows would be under Carrano's "else"
         if ( stack.empty() )
            break;           // Exit the processing loop
         else
         {  cur = stack.pop ( );
            if ( front == null )
               front = tail = cur;
            else
               tail = tail.right = cur;
            cur.left = null;
            cur = cur.right;
         }
      }
      root = front;
   }

   // FORM BALANCED TREE

   {//Pseudo-root used; real root to the right
      Node pseudo = new Node(-1, null, root);
      int  m, nBack = n - 1;

      for ( m = nBack / 2; m > 0; m = nBack / 2 )
      {
         int  j = 0;
         Node scanner = pseudo;

         for ( j = 0; j < m; j++ )
         {//leftward rotation
            Node child = scanner.right;
            scanner.right = child.right;
            scanner = scanner.right;
            child.right = scanner.left;
            scanner.left = child;
         }  // end for j . . .
         nBack = nBack - m - 1;
      }  // end for m . . .
      root = pseudo.right;
   }
   return root;
}