public class Prog1
//generate a binary search trees and prints the leaves
{
	public static void main(String[] asd)
	{
		Trees t = new Trees();
		String line = "qwertyasdf";
		t.BinarySearchTree(line);
		System.out.println("infix traversal");
		t.infix();
		System.out.println("height is " + t.height() );
//		System.out.println("postfix traversal");
//		t.postfix();
		t.printLeaves();
		System.out.println();
	}
}

class Trees
{
	class Node
	{
		private Object info;
		private Node left, right;
	}
	
	private Node root;
	
	private boolean isLeaf(Node t)
	{
		return t.left == null && t.right == null;
	}
	
	
	public void BinarySearchTree(String line)
	{
		Node p = null, q;//p chases q
		char rootChar = line.charAt(0);
		root = subTree(new Character(rootChar) );
		int len = line.length();
		Object item;
		char ch;
		for(int j = 1; j < len; j++)
		{
			q = root;
			ch = line.charAt(j);
			item = new Character(ch);
			while(q != null)//see where item should be inserted
			{
				p = q;
				if( ("" + item).compareTo("" + q.info) < 0) 
				{
					q = q.left;
				}
				else
				{
					q = q.right;
				}
			}
			if( ("" + item).compareTo("" + p.info) <  0)//inseert item
			{
				p.left = subTree(item);
			}
			else
			{
				p.right = subTree(item);
			}
		}
	}
			
	
	private Node subTree(Object item)
	{
		Node temp = new Node();
	    temp.info = item;
	    temp.left = null;
	    temp.right = null;
	    return temp;
	 }
	 
	 
	 public void infix()
	 {
	 	infix(root);
	 	System.out.println();
	 }
	 
	 public void printLeaves()
	 {
	 	printLeaves(root);
	 	System.out.println();
	 }
	 
	 public void printLeaves(Node t)
	 {
	 	if(t != null)
	 	{
	 		printLeaves(t.left);
	 		if( isLeaf(t) )
	 		{
	 			System.out.println(t.info);
	 		}
	 		printLeaves(t.right);
	 	}
	 }
	 
	 private void infix(Node t)
	 {
	 	if(t != null)
	 	{
	 		infix(t.left);
	 		System.out.print(t.info);
	 		infix(t.right);
	 	}
	 }public int height()
	 {
	 	return height(root);
	 }
	 
	 private int height(Node t )
	 {
	 	if(t == null)
	 	{
	 		return -1;
	 	}
	 	else
	 	{
	 		return 1 + Math.max(height(t.right), height(t.left) );
	 	}
	 }
	 			
}