package BST_A2;

import java.util.TreeMap;

public class BST implements BST_Interface {
  public BST_Node root;
  int size;

  public BST(){ size=0; root=null; }

  @Override
  //used for testing, please leave as is
  public BST_Node getRoot(){ return root; }

@Override
public boolean insert(String s)  {

	if(root == null){

		root = new BST_Node(s);

		size++;
		return true;

	} else {

		if(root.containsNode(s)){

			return false;

		} else{

			root.insertNode(s);

			size++;

			return true;

		}
	}
}



@Override
public boolean remove(String s) {
	// check to see if you want to remove the data is the root node
	// if it is, make a new node, make the current root left child
	if (root == null)
		return false;
	else{
		if (root.data.compareTo(s)==0){
			BST_Node fakeRoot = new BST_Node(s);
			fakeRoot.left = root;
			boolean result = fakeRoot.left.removeNode(s,fakeRoot.left, fakeRoot);
			root = fakeRoot.getLeft();
			size --;
			return result;
		}

		else{
			if(root.removeNode(s, root, null)==true){
				size -=1;
				return true;
				}
			else{
				return false;
				}
			}
	}
}


@Override
public String findMin() {
	if (root == null){
		return null;
	} else {
		return root.findMin().getData();
	}
}


@Override
public String findMax() {
	if (root == null){
		return null;
	}else {
		return root.findMax().getData();
	}

}

@Override
public boolean empty() {
	return root == null;
}

@Override
public boolean contains(String s) {
	if(root == null){

		return false;

	} else {

		return root.containsNode(s);
	}
}


@Override
public int size() {
	return this.size();
}

@Override
public int height() {
	return getHeight(root);
}

public int getHeight(BST_Node node){
	  if (node == null) return -1;
	  return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}
}