Implement the remove(K key) method recursively

package trees;

import java.util.Comparator;

import interfaces.BinarySearchTree; import interfaces.Entry;

public class LinkedBinarySearchTree implements BinarySearchTree { /** * * @param - represents a key * @param - represents the value pointed by the key */ private class BTEntry implements Entry{ private K key; private V value;

public BTEntry(K key, V value) { super(); this.key = key; this.value = value; } public void setKey(K key) { this.key = key; }

public void setValue(V value) { this.value = value; }

@Override public K getKey() { return this.key; }

@Override public V getValue() { return this.value; }

} /** * Private class that will represent the nodes of the Tree. * Notice it differs from the TreeNode from the more general Tree and BinaryTree. * This is due to this one needing key-value pairs. * @author Manuel Rodriguez * * @param - represents a key * @param - represents the value pointed by the key */ private static class BTNode { private Entry value; private BTNode parent; private BTNode leftChild; private BTNode rightChild; public BTNode(Entry value, BTNode parent, BTNode leftChild, BTNode rightChild) { super(); this.value = value; this.parent = parent; this.leftChild = leftChild; this.rightChild = rightChild; } public Entry getValue() { return value; } public void setValue(Entry value) { this.value = value; } public BTNode getParent() { return parent; } public void setParent(BTNode parent) { this.parent = parent; } public BTNode getLeftChild() { return leftChild; } public void setLeftChild(BTNode leftChild) { this.leftChild = leftChild; } public BTNode getRightChild() { return rightChild; } public void setRightChild(BTNode rightChild) { this.rightChild = rightChild; } }

/* * BST Implementation starts here */ private BTNode root; private int size; private Comparator comp; // How do we initialize a BST? public LinkedBinarySearchTree() { this.root = null; this.size = 0; this.comp = new DefaultComparator(); } public LinkedBinarySearchTree(Comparator c) { this.root = null; this.size = 0; this.comp = c; }

/** * Adds a Node to the BST in its corresponding position. * If key is already in the BST it doesn't get added. * * @param key - key we want to add to the BST. Cannot be null. * @param value - Value associated to the given key we want to add. Cannot be null. */ @Override public void add(K key, V value) { // TODO Auto-generated method stub if(key == null || value == null) throw new IllegalArgumentException(); // Check if it's the BST is empty if(this.root == null) { this.root = new BTNode(new BTEntry(key, value), null, null, null); this.size++; return; } // Search for the position to place the entry and add it, if possible. recAdd(this.root, new BTEntry(key, value)); } /** * Recursive helper method for the add(). * @param n - Current node. The action we take is based on the key of this node. * @param e - Entry we want to add to the BST. */ private void recAdd(BTNode n, BTEntry e) { // Check the int res = comp.compare(n.getValue().getKey(), e.getKey()); if(res == 0) { return; } else if(res > 0) { if(n.getLeftChild() == null) { BTNode left = new BTNode(e, n, null, null); n.setLeftChild(left); this.size++; return; } recAdd(n.getLeftChild(), e); } else { if(n.getRightChild() == null) { BTNode right = new BTNode(e, n, null, null); n.setRightChild(right); this.size++; return; } recAdd(n.getRightChild(), e); } } /** * Returns the Entry that has the given key. Returns null if key not in the BST. * * @param key - key of the Entry we want to search for in the BST. * @return - Entry that has the given key. */ @Override public Entry get(K key) { if(key == null) throw new IllegalArgumentException(); return recGet(this.root, key); }

/** * Recurive helper method for the get(). Finds and returns the Entry with the given key. * @param n - Current node. We continue searching based on the key of this node. * @param key - Key we are searching for. * @return Entry with the given key. Null if not found. */ private Entry recGet(BTNode n, K key) { // TODO Auto-generated method stub if(n == null) return null; int res = comp.compare(key, n.getValue().getKey()); if(res == 0) return n.getValue(); else if(res remove(K key) {

//HERE } /** * Returns size of the BST. How many nodes it has. */ @Override public int size() { // TODO Auto-generated method stub return this.size; }

/** * Returns whether the BST is empty. */ @Override public boolean isEmpty() { // TODO Auto-generated method stub return this.root == null; }

/** * Prints the BST. It's printed from left to right, NOT top to bottom. * Root is the leftmost element. Left children will be below the root and right children will be above the root. */ public void print() { this.printAux(this.root, 0); }

private void printAux(BTNode N, int i) { if (N != null) { this.printAux(N.getRightChild(), i + 4); System.out.println(); for (int j=0; j

System.out.print(" "); } System.out.println(N.getValue().getKey()); this.printAux(N.getLeftChild(), i + 4); } }

}

REMOVING NODES remove('M'); - M must be replaced by D. - Do we need to do the in-order traversal to find the node to remove? Not really. - To find the in-order predecessor we: (10) Move to the left sub-tree of the node to remove. (Go left once) (1) Then we find the largest descendent of that sub-tree. (Go right until we can't) e reach a dead- end. (Last right child) REMOVNG NODES remove('M'); 'e reach a dead- end. (Last right child) REMOVING NODES remove('M'); - M must be replaced by D. - Do we need to do the in-order traversal to find the node to remove? Not really. - To find the in-order predecessor we: (10) Move to the left sub-tree of the node to remove. (Go left once) (1) Then we find the largest descendent of that sub-tree. (Go right until we can't) e reach a dead- end. (Last right child) REMOVNG NODES remove('M'); 'e reach a dead- end. (Last right child)