Как я могу исправить удалить способ на БСТ?

---

Мой метод удаления для BST работает неправильно. Я продолжаю получать исключения нулевого указателя и не думаю, что на самом деле что-то удаляю.

Вот мой класс, который использует этот основной метод:

import java.io.*;
import java.util.*;

///////////////////////////////////////////////////////////////////////////////
class BSTNode<T>
{	T key;
	BSTNode<T> left,right;
	BSTNode( T key, BSTNode<T> left, BSTNode<T> right )
	{	this.key = key;
		this.left = left;
		this.right = right;
	}
}

///////////////////////////////////////////////////////////////////////////////////////
class Queue<T>
{	LinkedList<BSTNode<T>> queue;
	Queue() { queue =  new LinkedList<BSTNode<T>>(); }
	boolean empty() { return queue.size() == 0; }
	void enqueue( BSTNode<T>  node ) { queue.addLast( node ); }
	BSTNode<T>  dequeue() { return queue.removeFirst(); }
	// THROWS NO SUCH ELEMENT EXCEPTION IF Q EMPTY
}

////////////////////////////////////////////////////////////////////////////////
class BSTreeP6<T>
{
	private BSTNode<T> root;
	private boolean addAttemptWasDupe=false;
	@SuppressWarnings("unchecked")
	public BSTreeP6( String infileName ) throws Exception
	{
		root=null;
		Scanner infile = new Scanner( new File( infileName ) );
		while ( infile.hasNext() )
			add( (T) infile.next() ); // THIS CAST RPODUCES THE WARNING
		infile.close();
	}

	public int size()
	{
		return countNodes(); 
	}

	// DUPES BOUNCE OFF & RETURN FALSE ELSE INCR COUNT & RETURN TRUE
	@SuppressWarnings("unchecked")
	public boolean add( T key )
	{	addAttemptWasDupe=false;
		root = addHelper( this.root, key );
		return !addAttemptWasDupe;
	}
	@SuppressWarnings("unchecked")
	private BSTNode<T> addHelper( BSTNode<T> root, T key )
	{
		if (root == null) return new BSTNode<T>(key,null,null);
		int comp = ((Comparable)key).compareTo( root.key );
		if ( comp == 0 )
			{ addAttemptWasDupe=true; return root; }
		else if (comp < 0)
			root.left = addHelper( root.left, key );
		else
			root.right = addHelper( root.right, key );

		return root;
    } // END addHelper


	// ITS A SEARCH - ONE OF FEW OPS YOU CAN DO ITERATIVELY
	public boolean contains( T key )
	{
		return contains( this.root, key  );
	}
	@SuppressWarnings("unchecked")
	private boolean contains( BSTNode<T> root, T key  )
	{
		if (root == null) return false;
		int comp = ((Comparable)key).compareTo( root.key );
		if ( comp == 0 ) return true;
		if (comp < 0) return contains(root.left, key );
		return contains(root.right, key );
	}

	public int countNodes()
	{
		return countNodes( root );
	}
	private int countNodes( BSTNode root)
	{
		if (root==null) return 0;
		return 1 + countNodes(root.left) + countNodes(root.right);
	}
		
	public int countLevels()
	  {
		return countLevels( root ); 
	  }
	  private int countLevels( BSTNode root)
	  {
		if (root==null) return 0;
		return 1 + Math.max( countLevels(root.left), countLevels(root.right) );
	  }
	  
	  public int[] calcLevelCounts()
	  {
		int levelCounts[] = new int[countLevels()];
		calcLevelCounts( root, levelCounts, 0 );
		return levelCounts;
	  }
	  private void calcLevelCounts( BSTNode root, int levelCounts[], int level )
	  {
		if (root==null)return;
		++levelCounts[level];
		calcLevelCounts( root.left, levelCounts, level+1 );
		calcLevelCounts( root.right, levelCounts, level+1 );
	  }

	// INORDER TRAVERSAL REQUIRES RECURSION
	public void printInOrder()
	{
		printInOrder( this.root );
		System.out.println();
	}
	private void printInOrder( BSTNode<T> root )
	{
		if (root == null) return;
		printInOrder( root.left );
		System.out.print( root.key + " " );
		printInOrder( root.right );
	}

	public void printLevelOrder()
	{	if (this.root == null) return;
		Queue<T> q = new Queue<T>();
		q.enqueue( this.root ); // this. just for emphasis/clarity
		while ( !q.empty() )
		{	BSTNode<T> n = q.dequeue();
			System.out.print( n.key + " " );
			if ( n.left  != null ) q.enqueue( n.left );
			if ( n.right != null ) q.enqueue( n.right );
		}
	}

	// # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
	// DO NOT MODIFY ANYTHING ABOVE THIS LINE.  YOU FILL IN ALL THE CODE BELOW
	// # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

	// return true only if it finds/removes the node
	public boolean remove( T key2remove )
	{
		
		return remove(this.root, key2remove);			  
	}
	private BSTNode<T> miniElement(BSTNode<T> root)
	{
		if(root.left == null)
			return root;
		else
			return miniElement(root.left);
	}
	private BSTNode<T> removeMin(BSTNode<T> root) 
	{
		if (root.left != null) 
		{
			return removeMin(root.left);
		} 
		if(root.right == null)
		{
			root.left = null;
		} 
		else 
		{ 
			root.left = removeMin(root.right);
		}
		return root;
	}
	@SuppressWarnings("unchecked")
	private boolean remove (BSTNode<T> root, T key2remove)
	{
		if(root == null)
			return false;

		T rootData = root.key;
		int comp = ((Comparable)key2remove).compareTo(rootData);
		if (comp == 0) 
		{
				if (root.left == null && root.right == null) 
				{
					root = null;
					return true;
				} 
				else if (root.left != null && root.right != null) 
				{
					BSTNode<T> temp = root;
					BSTNode<T> thing = miniElement(root.left);
					root.key = thing.key;
					removeMin(root.right);
					return true;
				}
				else if(root.left == null && root.right != null)
				{
					root= root.right;
					return true;
				}
				else if(root.left != null && root.right == null)
				{
					root = root.left;
					return true;
				}
				
		}
		if (comp < 0) 
		{
			if (root.left.key.equals(key2remove)) 
			{
				if (root.left.left == null || root.left.right == null) 
				{
					root.left = null;
					return true;
				}
				else if (root.left.left != null && root.left.right != null) 
				{
					BSTNode<T> temp = root.left;
					BSTNode<T> thing = miniElement(root.left.left);
					root.key = thing.key;
					removeMin(root.left.right);
					return true;
				}
				else if(root.left.left == null && root.left.right != null)
				{
					root.left = root.left.right;
					return true;
				}
				else if(root.left.left != null && root.left.right == null)
				{
					root.left = root.left.left;
					return true;
				}
			}
			return remove(root.left, key2remove);
		}
		 if (comp > 0) 
		 {
				if (root.right.key.equals(key2remove)) 
				{
					if (root.right.right == null || root.right.left == null) 
					{
						root.right = null;
						return true;
					}
					else if (root.right.left != null && root.right.right != null) 
					{
						BSTNode<T> temp = root.right;
						BSTNode<T> thing = miniElement(root.right.left);
						root.key = thing.key;
						removeMin(root.right.right);
						return true;
					}
					else if(root.right.left == null && root.right.right != null)
					{
						root.right = root.right.right;
						return true;
					}
					else if(root.right.left != null && root.right.right == null)
					{
						root.right = root.right.left;
						return true;
					}
				}
				return remove(root.right, key2remove);
		 }
		 return false;
	}
		
}

Вот основной метод:

public class BSTesterP6
{
	public static void main( String[] args ) throws Exception
	{
		BSTreeP6<String> tree1 = new BSTreeP6<String>( args[0] );
		System.out.format( "\ntree1: loaded from %s contains %d nodes on %d levels:\n", args[0], tree1.countNodes(), tree1.countLevels() );
		System.out.print("IN ORDER tree1:    "); tree1.printInOrder();
		System.out.print("LEVEL ORDER tree1: "); tree1.printLevelOrder();
		int[] levelCounts = tree1.calcLevelCounts();
		System.out.println();
		for (int i = 0 ; i<levelCounts.length; ++i )
			System.out.format("level:%2d   %d\n",i,levelCounts[i] );
		
		
		// REMOVE SEVERAL NODES WHO HAVE 2 CHILDREN
		tree1.remove( "C" ); tree1.remove( "I" ); tree1.remove( "P" ); 	tree1.remove( "W" ); // ALL HAVE 2 CHILDREN
		
		System.out.format( "\ntree1: after removing C, I, P, W, contains %d nodes on %d levels:\n", tree1.countNodes(), tree1.countLevels() );
		System.out.print("IN ORDER tree1:    "); tree1.printInOrder();
		System.out.print("LEVEL ORDER tree1: "); tree1.printLevelOrder();	
		levelCounts = tree1.calcLevelCounts();
		System.out.println();
		for (int i = 0 ; i<levelCounts.length; ++i )
			System.out.format("level:%2d   %d\n",i,levelCounts[i] );
		
		
		// REMOVE SEVERAL lEAVES
		tree1.remove( "J" ); tree1.remove( "S" ); tree1.remove( "Z" ); // ALL ARE LEAVES
		
		System.out.format( "\ntree1: after removing J, S, Z, contains %d nodes on %d levels:\n", tree1.countNodes(), tree1.countLevels() );
		System.out.print("IN ORDER tree1:    "); tree1.printInOrder();
		System.out.print("LEVEL ORDER tree1: "); tree1.printLevelOrder();
		levelCounts = tree1.calcLevelCounts();
		System.out.println();
		for (int i = 0 ; i<levelCounts.length; ++i )
			System.out.format("level:%2d   %d\n",i,levelCounts[i] );

		// REMOVE SEVERAL NODES WHICH HAVE EXACTLY ONE CHILD
		tree1.remove( "D" ); tree1.remove( "K" ); tree1.remove( "R" ); tree1.remove( "Y" ); // THESE HAVE EXACTLY 1 CHILD

		System.out.format( "\ntree1: after removing D, K, R, Y, contains %d nodes on %d levels:\n", tree1.countNodes(), tree1.countLevels() );
		System.out.print("IN ORDER tree1:    "); tree1.printInOrder();
		System.out.print("LEVEL ORDER tree1: "); tree1.printLevelOrder();
		levelCounts = tree1.calcLevelCounts();
		System.out.println();
		for (int i = 0 ; i<levelCounts.length; ++i )
			System.out.format("level:%2d   %d\n",i,levelCounts[i] );

		System.out.println();
		System.out.println( "Now attempting remove of A..Z");
		String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
		for ( int i=0 ; i<alphabet.length() ; ++i )
		{
			if ( tree1.remove(alphabet.charAt(i)+"") )
			{
				System.out.format("\nremove(%c) successful: ", alphabet.charAt(i) ); 
				tree1.printLevelOrder();
			}
			else
			{
				System.out.format("\nremove(%c) failure:    ", alphabet.charAt(i) );
				tree1.printLevelOrder();
			}
		}
	}
}

Вот выходной файл

            M
     F             T
  C     I      P      W
A  D  G   K  N   R  U   Y
 B  E  H J L  O Q S  V X Z

Что я уже пробовал:

I need help figuring it out. 

---