start(){
remove(max(root), root);
remove(max(root), root);
}
remove (String key, node position)
{
if(root == null) return;
if(position.key > key){
remove(key, position.left); //keep searching for key node on left
}
else {
if(position.key < key){
remove(key, position.right); //keep searching for key node on right
}
else {
if (position.left != null && position.right != null)
{
next_max_node = max(position.right);
position.key = next_max_node.key;
remove (next_max_node.key, position.right); //next goes onto remove next_max_node value
}
else if(position.left != null) {
position = position.left;
}
else if(position.right != null) {
position = position.right;
}
else {
position = null;
}
}
}
}
max(node)
{
maxnode = node;
while(maxnode.right != null){
maxnode = maxnode.right;
}
return maxnode;
}