public class Prog5
//searching for a given letter on a BST using comparable
{
	public static void main(String[] asd)
	{
		Trees t = new Trees();
		String line = "qwertyasdf";
		int len = line.length();
		Comparable[] z = new Comparable[len];
		for(int j = 0; j < len; j++)
		{
			z[j] = new Character(line.charAt(j) );
		}
		t.BinarySearchTree(z);
		System.out.println("infix traversal");
		t.infix();
		ConsoleReader kbd = new ConsoleReader();
		System.out.println("Search for what letter?");
		char target = (kbd.readLine()).charAt(0);
		boolean found = t.search(new Character(target));
		if(found)
		{
			System.out.println(target + " was found");
		}
		else
		{
			System.out.println(target + " was not found");
		}	
	}
}

class Trees
{
	class Node
	{
		Comparable info;
		Node left, right;
	}
	
	Node root;
	boolean found  = false;
	
	public boolean search(Comparable c)
	{
		 search(root, c);
		return found;
	}
	
	public void search(Node t, Comparable c)
	{
		if( t != null && !found )
		{
			if( t.info.equals(c))
			{
				found = true;
			}
			else if( c.compareTo(t.info) > 0 )
			{
				search( t.right, c);
			}
			else
			{				
				search( t.left, c);
			}
		}
	}
		
	
	
	
	public void BinarySearchTree(Comparable[] z)
	{
		Node p = null, q;//p chases q
		root = subTree(z[0]);
		int len = z.length;
		for(int j = 1; j < len; j++)
		{
			q = root;
			while(q != null)//see where item should be inserted
			{
				p = q;
				if( (z[j]).compareTo(q.info) < 0) 
				{
					q = q.left;
				}
				else
				{
					q = q.right;
				}
			}
			if( (z[j]).compareTo( p.info) <  0)//inseert item
			{
				p.left = subTree(z[j]);
			}
			else
			{
				p.right = subTree(z[j]);
			}
		}
	}
			
	
	public Node subTree(Comparable 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 infix(Node t)
	 {
	 	if(t != null)
	 	{
	 		infix(t.left);
	 		System.out.print(t.info + " ");
	 		infix(t.right);
	 	}
	 }
}