package ddAsBST;

public class DynamicDict {
	private BSTNode root; 
	
	
	public DynamicDict(){
		root = null;
	}
	
	
	public boolean isEmpty(){
		if(root==null){
			return true;
		}else{
			return false;
		}
	}
	
	
	public String find(int key){
		return find(key,root);
	}
	
	public String find(int key,BSTNode currentNodeConsidered){
		if(currentNodeConsidered==null){
			return "Woah bro, invalid key";
		}
		if(currentNodeConsidered.key==key){
			return currentNodeConsidered.data;
		}
		if(currentNodeConsidered.key<key){
			return find(key,currentNodeConsidered.right);
		}else{
			return find(key,currentNodeConsidered.left);
		}
	}
	
	public void insert(int key, String data){
		root = insert(key, data, root);		
	}
	
	public BSTNode insert(int key, String data, BSTNode currentNodeConsidered){
		// will occur when insert is finally called on node who has a null child
		if (currentNodeConsidered==null){ //and in one instance when the node is initialized  
			return new BSTNode(key, data,null, null);
		}
		//otherwise, we traverse down the tree (consider the children)
		//this all starts starting with the left and right of the root
		if(key>currentNodeConsidered.key){
			//if the key is greater than the current node's we attempt to insert as the currentNode's right node. 
			//if the right node is null, then it'll be added as such. If it's not null, it'll repeat the process 
			//for that node, perhaps considering the left case. 
			currentNodeConsidered.right= insert(key,data,currentNodeConsidered.right);
		}else{ 
			currentNodeConsidered.left = insert(key,data,currentNodeConsidered.left);
		}
		return currentNodeConsidered; //this should take care of the stack of recursive calls 
		//other than the innermost one. That is, it leaves everything as it was up the stack. 
		
	}
	
	public void remove(int key){
		remove(key,root);
	}
	
	public BSTNode remove(int key, BSTNode currentNodeConsidered){
		if(currentNodeConsidered==null){
			System.out.println("Um, no node with that key.");
			return null;
		}
		if(key<currentNodeConsidered.key){
			currentNodeConsidered.left=remove(key,currentNodeConsidered.left);
		}
		if(key>currentNodeConsidered.key){
			currentNodeConsidered.right=remove(key,currentNodeConsidered.right);
		}
		if(key==currentNodeConsidered.key){//we found what we need to remove
			//System.out.println("That key, "+key+", was found!");
			if(currentNodeConsidered.left==null&&currentNodeConsidered.right==null){//if it's a leaf
				currentNodeConsidered=null; //the deletion is done
			}else if(currentNodeConsidered.left==null){//Just the left is null
				currentNodeConsidered=currentNodeConsidered.right;
			}else if(currentNodeConsidered.right==null){//Just the right is null
				currentNodeConsidered=currentNodeConsidered.left;
			}else{
				//Replacing with the max of the left subtree or min of right subtree are viable options
				BSTNode valueToReplaceWith = findMax(currentNodeConsidered.left);
				currentNodeConsidered.key=valueToReplaceWith.key;
				currentNodeConsidered.data=valueToReplaceWith.data;
				currentNodeConsidered.left=remove(valueToReplaceWith.key,currentNodeConsidered.left);
			}		
		}
		return currentNodeConsidered;
	
	}
	
	
	
	public BSTNode findMax(BSTNode rootOfSubtree){
		while(rootOfSubtree.right!=null){
			rootOfSubtree=rootOfSubtree.right;
		}
		return rootOfSubtree;
	}
	
	
	public int count(){
		return count(root);
	}
	
	public int count(BSTNode rootOfSubtree){

		if(rootOfSubtree.left==null&&rootOfSubtree.right==null){
			return 1;
		}else if(rootOfSubtree.left==null){
			return 1+count(rootOfSubtree.right);
		}else if(rootOfSubtree.right==null){
			return 1+count(rootOfSubtree.left);
		}else{//has two children
			return 1+count(rootOfSubtree.right)+count(rootOfSubtree.left);
		}
	}
	
	public int height(){
		return height(root);
	}
	
	public int height(BSTNode rootOfSubtree){
		if(rootOfSubtree.left==null&&rootOfSubtree.right==null){
			return 1;
		}else if(rootOfSubtree.left==null){
			return 1+height(rootOfSubtree.right);
		}else if(rootOfSubtree.right==null){
			return 1+height(rootOfSubtree.left);
		}else{//has two children
			return 1+Math.max(height(rootOfSubtree.right),height(rootOfSubtree.left));
		}
	}
	
	
	
	
	/*
	
	public String findMin(int key){
		BSTNode currentNodeOfInterest = root;
		while(currentNodeOfInterest.left!=null){
			currentNodeOfInterest=currentNodeOfInterest.left;
		}
		return currentNodeOfInterest.data;
	}
	
	*/
	
}