public class Trees5
//makes a mirror image of tree, counts nodes using an int method
{  public static void main(String[] as)
   {  Tree2 t1 = new Tree2();
      ConsoleReader kbd = new ConsoleReader();
	  System.out.println("Type the letters to be sorted");
	  String line = kbd.readLine();   
      t1.sort(line);
	  t1.printInfix(); 
	  System.out.println();
	  System.out.println("the node count is "+t1.countTheNodes() );
	  t2.copyTree(t1);
	  System.out.println("Infix traversal of copy of the tree is:");
	  t2.printInfix();
	  System.out.println();
	  Tree2 t3 = new Tree2();
	  t3.reverseTree(t1);	  
	  System.out.println("Infix traversal of mirror of the tree is:");
	  t3.printInfix();
	  System.out.println();
   }
}
   
class Tree2 
{ Node root;
   
     public Tree2()
     {  root = null;
     }
	 
	 public void copyTree(Tree2 T)
	 {  Node t = T.root;
	    Node t1 =  copy(t);
		this.root = t1;
	 }
	 
	 private Node copy(Node t)
	 { Node q, r, s;
	   q = null;
	   if (t != null) 
	   {  r = copy(t.left);
	      s = copy(t.right);
		  q = new Node();
		  q.left = r;
		  q.right = s;
		  q.data = t.data;
	   }
	   return q;
	 } 
	 
	 public void reverseTree(Tree2 T)
	 {  Node t = T.root;
	    Node t1 =  reverse(t);
		this.root = t1;
	 }
	 
	 private Node reverse(Node t)
	 //makes a mirror image of tree
	 { Node q, r, s;
	   q = null;
	   if (t != null) 
	   {  r = reverse(t.left);
	      s = reverse(t.right);
		  q = new Node();
		  q.left = s;
		  q.right = r;
		  q.data = t.data;
	   }
	   return q;
	 } 
     private Node subTree(char item)
     {  Node t = new Node();
	    t.left = null;
		t.right = null;
		t.data = item;
		return t;
     }
	 
	 private boolean leaf(Node t)
	 { return t.left == null && t.right == null;
	 }
	 
	 public void printTheLeaves()
	 { Node t = this.root;
	   printLeaf(t);
	 }
	 
	 public int countTheNodes()
	 { Node t = this.root;
	   return count(t); 
	 }
	 
	 private int count(Node t)
	 { int n;
	   if( t == null)
	      n = 0;
	   else
		  n = count(t.left) + count(t.right) + 1;
	   return n;   
	 }
	 
	 public void printLeaf(Node t )
	 { if( t != null) 
	   { printLeaf(t.left);
	     if( leaf(t) ) System.out.print(t.data);
		 printLeaf(t.right);
	   }
	 }
	 
	 public void printInfix()
	 { Node t = this.root;
	   infix(t);	   
	 }	 	 
	 
	 public void infix(Node t)
	 { if (t != null)	 	 
	   { infix(t.left);
	     System.out.print( t.data);
		 infix(t.right);
	   }
	 }	 
	 
	 public void sort(String line)
	 { // Node root = this.tree;
	    int len = line.length();
	    this.root = subTree( line.charAt(0) );		
		for(int j = 1; j < len; j++)
		{ char letter = line.charAt(j);
	      Node p = null; 
		  Node q = root;
		  while ( q != null )
		  {   p = q;
		      if( letter < q.data)
			     q = q.left;
			  else
			     q = q.right;
		  }
		  if( letter < p.data)
		    leftTree(p, letter);
		  else
		    rightTree(p, letter);
		}
	 }				   

	  private void leftTree(Node p, char item)
	 {	p.left = subTree(item);
	 }
	 
	 private void rightTree(Node p, char item)
	 { p.right = subTree(item);
	 }
	 
     private class Node
     { public char data;
	   public Node left, right;
     }
}