public class BalanceAct
{// Does a breadth-first search
  public static void main(String[] grdsz)
  { Tree2 tree = new Tree2();
    ConsoleReader  kbd = new ConsoleReader();
	System.out.println("Type your stuff");
	String line = kbd.readLine();
	
    tree.binary(line);
	tree.printInfix();
	tree.adjust();
	tree.pwint(); 
	
  }
  
}

class Tree2
{ Node tree;

  private class Node  
  { char data;
  	int balance;
  	Node left, right;
  }
  
  public void adjust()
  {  Node t = this.tree;
     int height   = adjust(t);
  }
  
  private int adjust(Node t)
  {  int L, R;
     if( t == null)
  	    return -1;
	 else
	 {  L = adjust(t.left);
	    R = adjust(t.right);
		t.balance = L - R;
		return 1 + Math.max(L, R);	
	 }
  }
  
  private void pwint(Node t)
  { //prints node value and balance factor
    if ( t != null)
	{   pwint(t.left);
        System.out.println( t.data + " "+ t.balance);
		pwint(t.right);
	}
  }
  
  public void pwint()
  {  Node t = this.tree;
     pwint(t);
  }  
  
  
			
  
  
       
  
  
  public Node subTree(char item)
  {//creates a subtree
    Node t = new Node();
	t.data = item;
	t.left = null;
	t.right = null;
	return t;
  }
  
  public void leftTree(char item, Node p)
  { p.left = subTree(item);
  }
  
  public void rightTree(char item, Node p)
  { p.right = subTree(item);
  }
  
  public void binary(String line )
  //creates a bianty tree using iteration
  {  int len = line.length();
  	 char ch;
  	 Node root = subTree( line.charAt(0) );
	 Node p = null, q;
	 for(int j = 1; j < len; j++)	 
	 {  ch =  line.charAt(j);
		q = root;
		while ( q != null)
		{  p = q;
	       if( ch < q.data)
		      q = q.left;
		   else
		      q = q.right;
		}
		if(ch < p.data)
		   leftTree(ch, p);
		else
		   rightTree(ch, p);
	 }
	 this.tree = root;
  }		   
  
  private void infix(Node t )
  {  if( t != null)
     { infix(t.left);
	   System.out.print( t.data);
	   infix(t.right);
     }
  } 
  
  public void printInfix()
  {  Node root = this.tree;
     infix(root);
  }
}