C         A. Colin Day, "Balancing a Binary Tree",
C         COMPUTER JOURNAL Vol. 19 (1976), pp. 360-61.
C
      SUBROUTINE BALNCE(ILPT,IRPT,N,IROOT)
C
C         BALANCES A TREE OF N ITEMS.
C            ILPT(N) - LEFT POINTERS
C            IRPT(N) - RIGHT POINTERS
C            IROOT - ROOT OF TREE (CHANGED BY SUBROUTINE)
C
      DIMENSION ILPT(N), IRPT(N)
C
C         STRIP ITEMS FROM TREE AS LIST
C         tjr:  in-order traversal of a threaded binary tree
C
      IF ( N .LE. 1) RETURN
      ISTRT = 0
      J = IROOT
      GO TO 20
C FOLLOW LEFT POINTERS
   10 J = ILPT(J)
   20 IF (ILPT(J) .GT. 0) GO TO 10
C THIS ITEM IS TO BE STRIPPED
      IF (ISTRT .GT. 0) GO TO 30
C FIRST ITEM - KEEP TRACK OF START
      ISTRT = J
      GO TO 40
C NOT FIRST - CHAIN TOGETHER
   30 IRPT(LAST) = J
   40 ILPT(J) = 0
      LAST = J
C TEST FOR BACKTRACK, END OR RIGHT BRANCH
      J = IRPT(J)
      IF (J) 50, 60, 20
C BACKTRACK   tjr:  threaded binary tree
   50 J = -J
      GO TO 30
C
C         FORM BALANCED TREE
C
C SET LENGTH OF BACKBONE
   60 NBACK = N - 1
C FIND NO. OF TRANSFORMATION
   70 M = NBACK / 2
      IF ( M .LE. 0 ) RETURN
C INITIALISE FOR LOOP
      J = IROOT
      L = J
C MOVE ON ROOT IN ANTICIPATION
      IROOT = IRPT(IROOT)
C PERFORM TRANSFORMATIONS
      DO 80 I = 1, N
      K = IRPT(J)
      IRPT(L) = K
      IRPT(J) = ILPT(K)
      ILPT(K) = J
      L = K
   80 J = IRPT(K)
C AMEND LENGTH OF BACKBONE
      NBACK = NBACK - M - 1
      GO TO 70
      END

 
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;
}