My remove method for the BST is not working correctly. I keep getting null pointer exceptions and I don't think I am actually removing anything.
Here is my the class that that main method uses:
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(); }
}
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() );
infile.close();
}
public int size()
{
return countNodes();
}
@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;
}
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 );
}
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 );
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 );
}
}
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;
}
}
Here is the main method:
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] );
tree1.remove( "C" ); tree1.remove( "I" ); tree1.remove( "P" ); tree1.remove( "W" );
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] );
tree1.remove( "J" ); tree1.remove( "S" ); tree1.remove( "Z" );
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] );
tree1.remove( "D" ); tree1.remove( "K" ); tree1.remove( "R" ); tree1.remove( "Y" );
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();
}
}
}
}
Here is the output file
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
What I have tried:
I need help figuring it out.