// Name: TOM RAUSCHER
// Date: 1/28/08 
// BSTree.java
// Java AB Period 9
//BSTree Program

import java.util.*;
public class BSTree
{
	 private TreeNode root;
	
	public BSTree()
	{
	  root = null;
	}
	
	public void add(Comparable obj)
	{
		BSTNode newNode = new BSTNode(obj);
		
		if(root == null)
			root = newNode;
		else
			addNode (root, newNode);
	}
	
	private void addNode(TreeNode current, TreeNode newNode)
	{
		if(((Comparable)(newNode.getValue())).compareTo(current.getValue())  < 0)
		{
			if(current.getLeft() == null)
				current.setLeft(newNode);
			else
				addNode ((BSTNode)current.getLeft(), newNode);
		}
		else
		{
			if(current.getRight() == null)
				current.setRight(newNode);
			else
				addNode ((BSTNode)current.getRight(), newNode);
		}
	}
	
	public String toString()
	{
		return toString(root);
	}
	
	private String toString(TreeNode current)
	{
		String str = "";
		
		if(current.getLeft()!=null)
			str += toString(current.getLeft()) + "\n";
		
		str +=current.getValue();
		
		if(current.getRight()!=null)
			str += "\n" + toString(current.getRight());
		
		return str;
	}
	
	public int count()
	{
		
		return 0;
	}
	
	private int countNode(TreeNode n){
	
	
		return 0;
	}
	
	public int height()
	{
		
		return 0;
	}
	
	private int countHeight(TreeNode n)
	{
		
		return 0;
	}
	
	public int numLeaf()
	{
		
		return 0;
	}
	
	private int countLeaf(TreeNode n)
	{
		
		return 0;
	}
	
	public String preOrder()
	{
		return preOrder(root);
	}
	
	private String preOrder(TreeNode n)
	{
		String str = "";

		str += n.getValue();
		
		if(n.getLeft()!=null)
			str += " " + preOrder(n.getLeft());

		if(n.getRight()!=null)
			str += " " + preOrder(n.getRight());
		
		return str;
	}
	
	public String postOrder()
	{
		return postOrder(root);
	}
	
	private String postOrder(TreeNode n)
	{
		String str = "";
		
		if(n.getLeft()!=null)
			str += postOrder(n.getLeft()) + " ";

		if(n.getRight()!=null)
			str += postOrder(n.getRight()) + " ";
		
		str += n.getValue();
		
		return str;
	}
	
	public String inOrder()
	{
		return inOrder(root);
	}
	
	private String inOrder(TreeNode n)
	{
		String str = "";
		
		if(n.getLeft()!=null)
			str += inOrder(n.getLeft()) + " ";
		
		str +=n.getValue();
		
		if(n.getRight()!=null)
			str += " " + inOrder(n.getRight());
		
		return str;
	}
	
	public TreeNode largest()
	{
	
	
		return null;	
	}
	
	public TreeNode smallest()
	{
	
		return null;	
	}
	
	public boolean contains(String n){
		
		return false;	
	}
	
	private boolean doesContain(String n, TreeNode tn)
	{
	
		return false;
		
	}
	
	public String longestPath()
	{
		
		return null;
	}
	
	private String findLongest(TreeNode n)
	{
		
		return "";
	}
	
	public void delete(Comparable target)
	{
		 
		 
	}
	public TreeNode deleteHelper(TreeNode node, Comparable target)
	{
		
		
		return "josh is a huge freud";
	}
	
	public TreeNode deleteTargetNode(TreeNode target)
	{
		
		
		return null;
	}

}