I am having a problem deleting nodes from my Binary search tree. What I have so far does part of what it is supposed to do. I read in an input (paragraph of text) to create the tree (organized via ASCII character values). I make it, then print out all the elements. Then I need to delete the ones that begin with a vowel. MY algorithm deletes most of the ones that start with a vowel, but I believe that as it replaces values with other ones some of the words slip through. Here is my class. it is quite a bit of code, but the deletion part is from lines 43-81

```
package assign2;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.regex.Pattern;
public class Main {
public static void main(String[] args) {
Node binRoot = null, avlRoot = null;
try {
Scanner s = new Scanner (new File("Files/input.txt"));
s.useDelimiter("\\W");
while (s.hasNext()){
String st = s.next();
binRoot = addbin(binRoot, st);
avlRoot = insertavl(st, avlRoot);
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
System.out.print("BST: ");
printInOrder(binRoot);
System.out.println("\n");
System.out.print("AVL: ");
printInOrder(avlRoot);
System.out.println("\n");
System.out.print("DBST ");
binRoot = delete(binRoot);
printInOrder(binRoot);
//System.out.println(avlRoot.getPayload());
//printTree(root);
}
public static Node delete(Node n){
if (n == null)
return n;
if (("" + n.getPayload().charAt(0)).matches("[aeiouAEIOU]")){
if (n.goLeft() != null && n.goRight() != null){
n.takeOver(successor(n));
n.setRight(delete(n.goRight()));
}
else
if(n.goLeft() != null)
n = n.goLeft();
else
n = n.goRight();
}
try{
n.setLeft(delete(n.goLeft()));
}catch(NullPointerException e){}
try{
n.setRight(delete(n.goRight()));
}catch(NullPointerException e){}
return n;
}
private static Node successor(Node n) {
if (n.goRight() != null){
n = n.goRight();
while (n.goLeft() != null){
n = n.goLeft();
}
return n;
}
if (n.goLeft() != null)
return n.goLeft();
return null;
}
// Creates the avl tree
public static Node insertavl(String cont, Node n){
if (cont.length() != 0){
if (n == null){
n = new Node(null, cont, null);
}
else if (n.getPayload().compareTo(cont) > 0){
n.setLeft(insertavl(cont, n.goLeft()));
if (height(n.goLeft()) - height(n.goRight()) == 2){
if (n.getPayload().compareTo(cont) > 0){
// outside insert
n = sRotateToRight(n);
}
else{
// inside insert
n = dRotateToRight(n);
}
}else{
n.height = 1 + Math.max(height(n.goLeft()), height(n.goRight()));
}
}
else if (n.getPayload().compareTo(cont) < 0){
// right subtree
n.setRight(insertavl(cont, n.goRight()));
if (height(n.goLeft()) - height(n.goRight()) == 2){
if (n.getPayload().compareTo(cont) > 0){
// outside insert
n = sRotateToLeft(n);
}
else{
// inside insert
n = dRotateToLeft(n);
}
}else{
n.height = 1 + Math.max(height(n.goLeft()), height(n.goRight()));
}
}
else
n.incrementCounter();
return n;
}
return n;
}
private static Node dRotateToRight(Node n) {
n.setLeft(sRotateToLeft(n));
n = sRotateToRight(n);
return n;
}
private static Node dRotateToLeft(Node n){
n.setRight(sRotateToRight(n));
n = sRotateToLeft(n);
return n;
}
private static Node sRotateToRight(Node n) {
Node k1;
k1 = n.goLeft();
n.setLeft(k1.goRight());
k1.setRight(n);
n.height = 1 + Math.max(height(n.goLeft()), height(n.goRight()));
k1.height = 1 + Math.max(height(k1.goLeft()), k1.height);
n = k1;
return n;
}
private static Node sRotateToLeft(Node n){
Node k1;
k1 = n.goRight();
n.setRight(k1.goLeft());
k1.setLeft(n);
n.height = 1 + Math.max(height(n.goLeft()), height(n.goRight()));
k1.height = 1 + Math.max(height(k1.goLeft()), k1.height);
return n;
}
private static int height(Node h) {
if (h == null)
return -1;
return h.height;
}
/*
* BST
*/
private static Node addbin(Node binRoot, String st) {
if (binRoot == null)
binRoot = new Node(null, removePunc(st), null);
else {
String stt = removePunc(st);
if (stt.length() != 0)
insertBST(binRoot, stt);
}
return binRoot;
}
private static void insertBST(Node n, String w) {
if (w.compareTo(n.getPayload()) < 0){
if (n.goLeft() == null){
n.setLeft(new Node(null, w, null));
return;
}
insertBST(n.goLeft(), w);
}
else if (w.compareTo(n.getPayload()) > 0){
if (n.goRight() == null){
n.setRight(new Node(null, w, null));
return;
}
insertBST(n.goRight(), w);
}
else
n.incrementCounter();
}
// remove special characters
private static String removePunc(String next) {
next = next.replaceAll(("\\W"), "");
return next;
}
/*
* Print trees in different ways
*
*/
private static void printTree(Node tree) {
String s = "Current: " + tree.getPayload();
try{
if (tree.goLeft() != null)
s += "\tChildren: " + tree.goLeft().getPayload();
else
s += "\tChildren: null";
if (tree.goRight() != null)
s += ", " + tree.goRight().getPayload();
else
s += ", null";
System.out.println(s);
printTree(tree.goLeft());
printTree(tree.goRight());
}catch(NullPointerException e){}
}
private static void printInOrder(Node tree){
try{
if (tree.goLeft() != null)
printInOrder(tree.goLeft());
System.out.print (tree.getPayload() + " (" + tree.getCount() + "), ");
if (tree.goRight() != null)
printInOrder(tree.goRight());
}catch(NullPointerException e){}
}
}
```

Here is the node class

```
package assign2;
public class Node {
private int counter = 0;
private String s;
private Node l, r;
public int height = 1;
public Node (Node left, String word, Node right){
counter = 1;
s = word;
l = left;
r = right;
System.out.println("New Node: " + word);
}
public int getCount(){
return counter;
}
public String getPayload(){
return s;
}
public Node goLeft(){
return l;
}
public Node goRight(){
return r;
}
public void incrementCounter(){
counter++;
}
public void setLeft(Node left){
l = left;
}
public void setRight(Node right){
r = right;
}
public void takeOver (Node n){
s = n.getPayload();
counter = n.counter;
}
}
```

and Here is the input text that I am using

```
Objective
You are going to compare the relative efficiency of storing a BST in AVL format over a standard BST configuration. You will effectively write 2 programs in parallel so the 2 systems can be compared.
The Assignment
Implement a BST which has a String element and thus represents the Key as well; add an integer variable C which will represent the number of occurrences of the element. Your BST should support the following operations. Insert, Delete, Find, InOrder and IntPathLength. Each of the preceding operations should be implemented recursively where appropriate. The function IntPathLength should recursively calculate the internal path length of the tree. In the event of like elements you are to increment the count C field.
Repeat the above implementation for a BST-AVL tree. Each operation where appropriate is recursive, the Find, InOrder and IntPathLength operations you implemented for the standard BST should work for the BST-AVL tree. The deletion process for both trees should be removal of the node from the tree. When printing during the traversal: when a word only appears once then just print the word followed by a space, if there are multiple occurrences, succeed the output with the count in brackets, e.g. Implement (??). Consider using multiple words per line to conserve paper.
```

Here is the output my code produces

```
<not important stuff. Prints when a new node was created>
BST: 2 (2), AVL (3), Assignment (1), BST (7), C (2), Consider (1), Delete (1), Each (2), Find (2), Implement (2), In (1), InOrder (2), Insert (1), IntPathLength (3), Key (1), Objective (1), Repeat (1), String (1), The (3), When (1), You (2), Your (1), a (7), above (1), add (1), an (1), and (3), appears (1), appropriate (2), are (3), as (1), be (3), both (1), brackets (1), by (1), calculate (1), can (1), compare (1), compared (1), configuration (1), conserve (1), count (2), deletion (1), during (1), e (1), effectively (1), efficiency (1), element (2), elements (1), event (1), field (1), followed (1), following (1), for (4), format (1), from (1), function (1), g (1), going (1), has (1), if (1), implementation (1), implemented (2), in (3), increment (1), integer (1), internal (1), is (1), just (1), length (1), like (1), line (1), multiple (2), node (1), number (1), occurrences (2), of (7), once (1), only (1), operation (1), operations (3), output (1), over (1), paper (1), parallel (1), path (1), per (1), preceding (1), print (1), printing (1), process (1), programs (1), recursive (1), recursively (2), relative (1), removal (1), represent (1), represents (1), should (5), so (1), space (1), standard (2), storing (1), succeed (1), support (1), systems (1), the (21), then (1), there (1), thus (1), to (3), traversal (1), tree (4), trees (1), using (1), variable (1), well (1), when (1), where (2), which (2), will (2), with (1), word (2), words (1), work (1), write (1), you (2),
AVL: 2 (2), AVL (3), Assignment (1), BST (7), C (2), Consider (1), Delete (1), Each (2), Find (2), Implement (2), In (1), InOrder (2), Insert (1), IntPathLength (3), Key (1), Objective (1), Repeat (1), String (1), The (3), When (1), You (2), Your (1), a (7), above (1), add (1), an (1), and (3), appears (1), appropriate (2), are (3), as (1), be (3), both (1), brackets (1), by (1), calculate (1), can (1), compare (1), compared (1), configuration (1), conserve (1), count (2), deletion (1), during (1), e (1), effectively (1), efficiency (1), element (2), elements (1), event (1), field (1), followed (1), following (1), for (4), format (1), from (1), function (1), g (1), going (1), has (1), if (1), implementation (1), implemented (2), in (3), increment (1), integer (1), internal (1), is (1), just (1), length (1), like (1), line (1), multiple (2), node (1), number (1), occurrences (2), of (7), once (1), only (1), operation (1), operations (3), output (1), over (1), paper (1), parallel (1), path (1), per (1), preceding (1), print (1), printing (1), process (1), programs (1), recursive (1), recursively (2), relative (1), removal (1), represent (1), represents (1), should (5), so (1), space (1), standard (2), storing (1), succeed (1), support (1), systems (1), the (21), then (1), there (1), thus (1), to (3), traversal (1), tree (4), trees (1), using (1), variable (1), well (1), when (1), where (2), which (2), will (2), with (1), word (2), words (1), work (1), write (1), you (2),
DBST 2 (2), Assignment (1), BST (7), C (2), Consider (1), Delete (1), Find (2), In (1), In (1), Key (1), Repeat (1), Repeat (1), String (1), The (3), When (1), You (2), Your (1), an (1), be (3), be (3), both (1), brackets (1), by (1), calculate (1), can (1), compare (1), compared (1), configuration (1), conserve (1), count (2), deletion (1), during (1), field (1), field (1), field (1), followed (1), following (1), for (4), format (1), from (1), function (1), g (1), going (1), has (1), just (1), just (1), length (1), like (1), line (1), multiple (2), node (1), number (1), paper (1), paper (1), paper (1), parallel (1), path (1), per (1), preceding (1), print (1), printing (1), process (1), programs (1), recursive (1), recursively (2), relative (1), removal (1), represent (1), represents (1), should (5), so (1), space (1), standard (2), storing (1), succeed (1), support (1), systems (1), the (21), then (1), there (1), thus (1), to (3), traversal (1), tree (4), trees (1), variable (1), well (1), when (1), where (2), which (2), will (2), with (1), word (2), words (1), work (1), write (1), you (2),
```

Like I stated my code deletes a portion but not all.

As you can see this is an assignment, but I have spent at least 5 hours trying to figure out why it doesn't delete correctly.

Any suggestions would be helpful.

Thank you for your time and help.