import java.lang.Math;

public class RefBasedBinaryTree {
	protected TreeNode root;

	public RefBasedBinaryTree() {
		this.root = null;
	}

	public void insert(Integer value){
		if (root==null) {
			root = new TreeNode(value);
		} else {
			insert(null, root, value);
		}
	}
	
	// not a balanced insert
	private void insert(TreeNode parent, TreeNode t, Integer value) {
		if (t==null) {
			if(parent.getLeft()==null) {
				parent.setLeft(new TreeNode(value));
			} else {
				parent.setRight(new TreeNode(value));
			}            
		} else {
			int htLeft = height(t.getLeft());
			int htRight = height(t.getRight());
			if (htLeft<htRight) {
				insert(t, t.getRight(), value);
			} else {
				insert(t, t.getLeft(), value);
			}
		}
	}

	private int height(TreeNode t) {
		if (t==null) {
			return -1;
		} else {
			int highest = Math.max(height(t.getLeft()), height(t.getRight()));
			return 1 + highest;
		}
	}

	/*
	* Purpose: prints the value at each TreeNode in this BinaryTree
	*          following an in-order traversal
	* Parameters: none
	* Returns: Nothing
	*/
	public void inOrder(){
		inOrder(root);
		System.out.println();
	}

	/*
	* Purpose: prints the value at each TreeNode in t,
	*          following an in-order traversal
	* Parameters: TreeNode t
	* Returns: Nothing
	*/
	private void inOrder(TreeNode t){
		if (t==null) {
			return;
		} else {
			inOrder(t.getLeft());
			System.out.print(t.getValue() + " ");
			inOrder(t.getRight());
		}
	}

	/*
	* Purpose: prints the value at each TreeNode in this BinaryTree
	*          following a pre-order traversal
	* Parameters: none
	* Returns: Nothing
	*/
	public void preOrder(){
		preOrder(root);
		System.out.println();
	}

	/*
	* Purpose: prints the value at each TreeNode in t,
	*          following a pre-order traversal
	* Parameters: TreeNode t
	* Returns: Nothing
	*/
	private void preOrder(TreeNode t){
		if (t==null) {
			return;
		} else {
			System.out.print(t.getValue() + " ");
			preOrder(t.getLeft());
			preOrder(t.getRight());
		}
	}

	/*
	* Purpose: returns a String reprensentation of this BinaryTree
	* Parameters: none
	* Returns: String - the representation
	*/
	public String toString() {
		return toString(root);
	}

	private String toString(TreeNode t) {
		if(t==null) {
			return "";
		} else {
			String s = "";

			s += toString(t.getLeft());
			s += t.getValue() + " ";
			s += toString(t.getRight());

			return s;
		}
	}


	public static void main(String[] args) {
		// use these trees to test the methods you will implement in Part II
		RefBasedBinaryTree emptyTree = new RefBasedBinaryTree();
		RefBasedBinaryTree myTree = new RefBasedBinaryTree();
		
		for(int i=2; i <= 9; i++) {
			myTree.insert(i);
		}

		myTree.preOrder();
		myTree.inOrder();
	}
}