public class Trees4
{// create a bst and copy it
  public static void main(String[] grdsz)
  { Tree3 tree = new Tree3();
    ConsoleReader  kbd = new ConsoleReader();
	System.out.println("Type your stuff");
	String line = kbd.readLine();
	
    tree.binary(line);
	System.out.println("Infix traversal");
	tree.printInfix();
	
	Tree3 tree1 = new Tree3();
	tree1.copyTree(tree);
	tree1.printInfix();
	
	
  }
  
}

class Tree3
{ Node root;

  private class Node  
  { char data;
  	Node left, right;
  }
  
  public void copyTree( Tree3 tree)
  {  Node t = tree.root;
     this.root = copy(t);
  }  
  
  
  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 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;
  	 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);
	 }
  }		   
  
  private void infix(Node t )
  {  if( t != null)
     { infix(t.left);
	   System.out.print( t.data);
	   infix(t.right);
     }
  } 
  
  public void printInfix()
  {  infix(root);
     System.out.println();  
  }
  
  public void printPostfix()
  {  postfix(root);
  }
  
  private void postfix(Node t )
  {  if( t != null)
     { postfix(t.left);	  
	   postfix(t.right);
	   System.out.print( t.data);
     }
  } 
}