import java.io.*;
import java.util.*;               // for Stack class
////////////////////////////////////////////////////////////////
class AVLTree
   {
   private AVLNode root;             // first node of tree
   private int size;

// -------------------------------------------------------------
   public AVLTree()                  // constructor
      { root = null; }            // no nodes in tree yet
// -------------------------------------------------------------
   public AVLNode find(int key)      // find node with given key
      {                           // (assumes non-empty tree)
      AVLNode current = root;               // start at root
      while(current.iData != key)        // while no match,
         {
         if(key < current.iData)         // go left?
            current = current.leftChild;
         else                            // or go right?
            current = current.rightChild;
         if(current == null)             // if no child,
            return null;                 // didn't find it
         }
      return current;                    // found it
      }  // end find()
// -------------------------------------------------------------
   public void insert(int id)
      {
      // Increase number of elements in tree
      size++;

      AVLNode newNode = new AVLNode();    // make new node

      // Fill in the fields of the newly created AVLNode
      newNode.iData = id;           // insert data
      newNode.balance = 0; 	    // a leaf node has balance 0
      newNode.height = 0;           // the height of a tree with just one node is 0

      if(root==null)                // no node in root
         root = newNode;
      else                          // root occupied
         {
         AVLNode current = root;       // start at root and walk down the tree
         AVLNode parent = null;

	 // An AVLStack is a stack that stores AVLNodes. It will be used
	 // to store the search path
	 AVLStack S = new AVLStack(size);

	 // Loop to walk down the tree, until current becomes null
	 // The nodes visited in this walk are stored in AVLStack
         while(current != null)             
            {
            	S.push(current);
            	parent = current;

            	if(id < current.iData)  // go left?
               		current = current.leftChild;
            	else                    // or go right?
               		current = current.rightChild;
            }  // end while


	 // Insert the node
        if(id < parent.iData)
        	parent.leftChild = newNode;
        else
		parent.rightChild = newNode; 


         // Walk back up the tree, by popping items from the AVLStack S
        int leftHeight, rightHeight;
        AVLNode pathNode;
	while(!S.isEmpty())
	{
		// This is the current node of the search path
		pathNode = S.pop();	

		// Compute its height and balance
		// First find the height of the left subtree
		if(pathNode.leftChild == null)
			leftHeight = -1;
		else
			leftHeight = pathNode.leftChild.height;

		// Then find the height of the right subtree
		if(pathNode.rightChild == null)
			rightHeight = -1;
		else
			rightHeight = pathNode.rightChild.height;

		// Set the balance of the node
		pathNode.balance = rightHeight - leftHeight;
		
		// Set the height of the subtree rooted at the node
		pathNode.height = 1 + max(leftHeight, rightHeight);

		// Check if balance is out of bounds. If so, break out
		// of the loop because rotations are needed
		if((pathNode.balance < -1) || (pathNode.balance > 1))
		{
			System.out.println("Tree is no longer AVL.");
			break;	
		}
	} // end while stack is non-empty

      }  // end else not root
   }  // end insert()

   // A helper function that returns the maximum of two integers
   int max(int x, int y)
   {
	if(x > y)
		return x;
	return y;
   }

// -------------------------------------------------------------
   public void displayTree()
      {
      AVLStack globalStack = new AVLStack(3*(size+1));
      globalStack.push(root);
      int nBlanks = 40;
      boolean isRowEmpty = false;
      System.out.println(
      "..............................................................................");
      while(isRowEmpty==false)
         {
         AVLStack localStack = new AVLStack(3*(size+1));
         isRowEmpty = true;

         for(int j=0; j<nBlanks; j++)
            System.out.print(' ');

         while(globalStack.isEmpty()==false)
            {
            AVLNode temp = (AVLNode)globalStack.pop();
            if(temp != null)
               {
               System.out.print(temp.iData+" ");
               System.out.print(temp.height+" ");
               System.out.print(temp.balance);
               localStack.push(temp.leftChild);
               localStack.push(temp.rightChild);

               if(temp.leftChild != null ||
                                   temp.rightChild != null)
                  isRowEmpty = false;
               }
            else
               {
               System.out.print("--");
               localStack.push(null);
               localStack.push(null);
               }
            for(int j=0; j<nBlanks*2-2; j++)
               System.out.print(' ');
            }  // end while globalStack not empty
         System.out.println();
         nBlanks /= 2;
         while(localStack.isEmpty()==false)
            globalStack.push( localStack.pop() );
         }  // end while isRowEmpty is false
      System.out.println(
      "..............................................................................");
      }  // end displayTree()
// -------------------------------------------------------------

  
}  // end class AVLTRee

  
////////////////////////////////////////////////////////////////