import java.util.ArrayList;
import java.util.Collections;

public class Tree
{
	private TreeNode root;

	public Tree()
	{
		root = null;
	}

	public Tree(ArrayList list)
	{
		root = arrayToTree(list,0,list.size()-1);
	}

	/**
	 * Returns a height-balanced tree containing values of list
	 * in range of indexes [left..right]; if list is sorted, this
	 * will be a search tree.
	 */
	public TreeNode arrayToTree(ArrayList list, int left, int right)
	{
		if (left <= right)
		{
		    int mid = (left+right)/2;
		    return new TreeNode(list.get(mid),arrayToTree(list,left,mid-1),
											  arrayToTree(list,mid+1,right));
		}
		return null;
    }

	public void add(Object o)
	{
		//try	// try/catch not in AP subset, so all of this is for enrichment
		//{
			root = addHelper(root,o);
		//}
		//catch(Exception e)	// all exceptions inherit from Exception
		//{e.printStackTrace();}// or whatever you want to do to deal with it
	}

	private TreeNode addHelper(TreeNode rt, Object o)
	{
		if (rt == null)
			return new TreeNode(o);

		// if o is < root's data, recursively insert on left subtree,
		// set current node's left to whatever's returned and then return
		// (modified) current node
		if (((Comparable)o).compareTo(rt.getValue()) < 0)
			rt.setLeft(addHelper(rt.getLeft(),o));
		else if (((Comparable)o).compareTo(rt.getValue()) > 0)
			rt.setRight(addHelper(rt.getRight(),o));
		else
			//System.err.println("Error - object " + o + " appears twice in tree");
			throw new IllegalStateException("Error - duplicate object " + o);

		// then return root back to caller
		return rt;
	}

	public boolean find(Object o)
	{
		return findHelper(root,o);
	}

	private boolean findHelper(TreeNode rt, Object o)
	{
		if (rt == null)
			return false;

		// if equal, return
		if (((Comparable)rt.getValue()).compareTo(o) == 0)
			return true;

		// if o < root's data, recursively find on left subtree
		if (((Comparable)rt.getValue()).compareTo(o) > 0)
			return findHelper(rt.getLeft(),o);
		// or right...
		return findHelper(rt.getRight(),o);
	}

	public Object findMax()
	{
		if (root == null)
			return null;

		TreeNode temp = root;
		while (temp.getRight() != null)
			temp = temp.getRight();
		return temp.getValue();
	}

	public void inOrder()
	{
		inOrderHelper(root);
	}

	private void inOrderHelper(TreeNode rt)
	{
		if (rt != null)
		{
			inOrderHelper(rt.getLeft());
			System.out.println(rt.getValue());
			inOrderHelper(rt.getRight());
		}
	}

	public void preOrder()
	{
		preOrderHelper(root);
	}

	private void preOrderHelper(TreeNode rt)
	{
		if (rt != null)
		{
			System.out.println(rt.getValue());
			preOrderHelper(rt.getLeft());
			preOrderHelper(rt.getRight());
		}
	}

	public void postOrder()
	{
		postOrderHelper(root);
	}

	private void postOrderHelper(TreeNode rt)
	{
		if (rt != null)
		{
			postOrderHelper(rt.getLeft());
			postOrderHelper(rt.getRight());
			System.out.println(rt.getValue());
		}
	}

	public int countNodes()
	{
		return countHelper(root);
	}

	private int countHelper(TreeNode rt)
	{
		if (rt == null)
			return 0;

		return 1 + countHelper(rt.getLeft()) + countHelper(rt.getRight());
	}

	public int countLeaves()
	{
		return leafHelper(root);
	}

	private int leafHelper(TreeNode rt)
	{
		if (rt == null)
			return 0;

		if (rt.getRight() == null && rt.getLeft() == null)
			return 1;

		return leafHelper(rt.getLeft()) + leafHelper(rt.getRight());
	}

	public int countDescendants()
	{
		return descHelper(root);	// or whatever
	}

	private int descHelper(TreeNode rt)
	{
		if (rt == null || (rt.getLeft() == null && rt.getRight() == null))
			return 0;

		if (rt.getLeft() != null && rt.getRight() != null)
			return 2 + descHelper(rt.getLeft()) + descHelper(rt.getRight());

		if (rt.getLeft() != null)
			return 1 + descHelper(rt.getLeft());

		return 1 + descHelper(rt.getRight());
	}

    public int height()
	{
		return heightHelper(root);
	}

	public int heightHelper(TreeNode rt)
	{
		if (rt == null)
			return 0;

		return 1 + Math.max(heightHelper(rt.getLeft()), heightHelper(rt.getRight()));
	}

	public boolean isBalanced()
	{
		return balanceHelper(root);
	}

	public boolean balanceHelper(TreeNode rt)
	{
		if (rt == null)
			return true;

		return balanceHelper(rt.getLeft()) && balanceHelper(rt.getRight()) &&
				Math.abs(heightHelper(rt.getLeft()) - heightHelper(rt.getRight())) <= 1;
    }

	public void remove(Object o)
	{
		root = removeHelper(root,o);
	}

	private TreeNode removeHelper(TreeNode rt, Object o)
	{
		if (rt == null)
			return null;

		// found it
		if (((Comparable)rt.getValue()).compareTo(o) == 0)
		{
			// if leaf return null to caller
			if (rt.getLeft() == null && rt.getRight() == null)
				return null;

			// if non-leaf and no left child return right child to caller
			if (rt.getLeft() == null)
				return rt.getRight();

			// if non-leaf and no right child return left child to caller
			if (rt.getRight() == null)
				return rt.getLeft();

			// must have two children - swap data from rightmost node in
			// left subtree and bypass node originally containing that data
			// then return the (modified) current node to caller
			TreeNode pos = rt.getLeft();	// go left once
			TreeNode prev = null;

			while (pos.getRight() != null)	// go as far right as possible
			{
				prev = pos;
				pos = pos.getRight();
			}

			root.setValue(pos.getValue());	// swap data

			if (prev != null)	// there was a right subtree
				prev.setRight(pos.getLeft());
			else
				rt.setLeft(rt.getLeft().getLeft());

			return rt;

			/*
			// must have two children - get data from rightmost node in
			// left subtree
			Object newData = getRightMost(root.getLeft());

			// create and return a new node with that data, the left subtree
			// with the node originally containing that data removed,
			// and the original right subtree
			return new TreeNode(newData,
								removeHelper(root.getLeft(),newData),
								root.getRight());
			*/
		}

		// if o < root's data, recursively delete on left subtree,
		// set current node's left to whatever's returned and then return
		// (modified) current node
		if (((Comparable)rt.getValue()).compareTo(o) > 0)
		{
			rt.setLeft(removeHelper(rt.getLeft(),o));
			return rt;
		}

		// o must be > so recursively delete on right subtree,
		// set current node's right to whatever's returned and then return
		// (modified) current node
		rt.setRight(removeHelper(rt.getRight(),o));
		return rt;
	}

	private Object getRightMost(TreeNode rt)	// for alternate remove implementation
	{
		// no right, return my data
		if (rt.getRight() == null)
			return rt.getValue();

		return getRightMost(rt.getRight());
	}

	// a reasonable attempt at a nice level-ordered print
	public String toString()
    {
		String result = "";
		int level = 0;
		String s;

		while ((s = levelString(root,level)) != null) {
	  		result += s + "\n";
			level++;
		}

		return result;
    }

    private String levelString(TreeNode rt, int level)
    {
		if (rt == null)
		    return null;

		if (level == 0)
		    return rt.getValue() + " ";

		String left = levelString(rt.getLeft(),level-1);
		String right = levelString(rt.getRight(),level-1);

		if (left == null && right == null)
			return null;

		String result = "";
		if (left != null)
			result += left;
		if (right != null)
			result += " " + right;
		return result;
    }

    public static void main(String[] args)
    {
    	Tree t = new Tree();
    	/*t.add("mark");
    	t.add("judy");
    	t.add("don");
    	t.add("anne");
    	t.add("josh");*/
    	ArrayList arr = new ArrayList();
    	arr.add("mark");
    	arr.add("judy");
    	arr.add("don");
    	arr.add("anne");
    	//arr.add("judy");	// for testing purposes
    	for (int i = 0; i < arr.size(); i++)
    		t.add(arr.get(i));
    	System.out.println("Inorder traversal:");
		t.inOrder();
    	System.out.println("\nPrint by level:\n" + t);

    	System.out.println("numLeaves = " + t.countLeaves());
    	System.out.println("numNodes = " + t.countNodes());
    	System.out.println("numDescendants = " + t.countDescendants());
    	System.out.println("hoser in tree? " + t.find("hoser"));
    	System.out.println("Max velue = " + t.findMax());
    	System.out.println();

    	Collections.sort(arr);	// sweet!
    	Tree t2 = new Tree(arr);
    	System.out.println("min-height tree on these values: \n" + t2);
	}
}