Having trouble removing from BST

Question

This is a relatively large project, but I'll try to put all necessary things here.

 /**  Removes the record with Key k from the dictionary. It throws a 
    DictionaryException if the record is not in the dictionary. */

public void remove(Key k) throws DictionaryException{

        deleteNode = findNode(k);
        if (deleteNode == null) throw new DictionaryException("Error: Record doesn't exist in the dictionary!");
        else{
            //check if children are leafs
            if(deleteNode.getLeftChild() == null || deleteNode.getRightChild() == null)
                //set it to itself
                replace = deleteNode;
            else
                //otherwise replace with successorNode
                replace = successorNode(deleteNode);
            //store left child if it exists
            if (replace.getLeftChild() != null)
                child = replace.getLeftChild();
            //else, store right
            else
                child = replace.getRightChild();
            //check if both nodes are null
            if (child != null) 
                child.setParent(replace.getParent());
            //else replace the node that needs to be deleted
            else{
                //replace left child of parent
                if(replace == replace.getParent().getLeftChild()) 
                    replace.getParent().setLeftChild(child);
                //else replace right
                else
                    replace.getParent().setRightChild(child);
            }   
            //store information of the replacing node, within the deleteNode
            if (replace != deleteNode) 
                deleteNode.setRoot(replace.getRecord());
        }
    }

This method has an null-pointer error on the parent stuff. I'm not sure how to go about dealing with it.

This is an Ordered Dictionary stored in a BST. Nodes consist of Records which consist of (Key,data) where Key is (name,type). Essentially a Record is ((name,type),data).

I can provide more information if necessary. I've been stuck here for a quite while any help is appreciated!

Answer 1

TreeBstNode: data structure

delete: delete method

public class TreeBst {

/**
 * The Class TreeBstNode.
 */
private class TreeBstNode {

    /** The data. */
    int data;

    /** The l child. */
    TreeBstNode lChild;

    /** The r child. */
    TreeBstNode rChild;

    /** The parent. */
    TreeBstNode parent;

    /**
     * Instantiates a new tree node.
     */
    TreeBstNode() {
        this(0, null, null, null);
    }

    /**
     * Instantiates a new tree node.
     * 
     * @param data
     *            the data
     * @param rChild
     *            the r child
     * @param lChild
     *            the l child
     * @param parent
     *            the parent
     */
    /**
     * @param data
     * @param rChild
     * @param lChild
     * @param parent
     */
    TreeBstNode(int data, TreeBstNode rChild, TreeBstNode lChild,
            TreeBstNode parent) {

        this.data = data;
        this.rChild = rChild;
        this.lChild = lChild;
        this.parent = parent;
    }

}

/** The root. */
private TreeBstNode root;

/**
 * Instantiates a new tree bst.
 */
public TreeBst() {
    root = null;
}

/**
 * Instantiates a new tree bst.
 * 
 * @param x
 *            the x
 */
public TreeBst(int x) {
    root = new TreeBstNode(x, null, null, null);
}
/**
 * Delete.
 * 
 * @param x
 *            the x
 * @return the tree node
 */
public TreeBstNode delete(int x) {
    return BST_Delete(root, x);
}
    /**
 * BS t_ delete.
 * 
 * @param t
 *            the t
 * @param x
 *            the x
 * @return the tree node
 */
private TreeBstNode BST_Delete(TreeBstNode t, int x) {
    // TODO Auto-generated method stub
    if (t == null) {
        return null;
    } else if (x < t.data) {
        BST_Delete(t.lChild, x);
    } else if (x > t.data) {
        BST_Delete(t.rChild, x);
    } else {
        return BST_DeleteItem(t);
    }
    return null;
}

/**
 * BS t_ delete item.
 * 
 * @param t
 *            the t
 * @return the tree node
 */
private TreeBstNode BST_DeleteItem(TreeBstNode t) {
    // TODO Auto-generated method stub
    TreeBstNode temp = t;
    TreeBstNode returnTree = null;
    if (t.lChild == null && t.rChild == null) {

        if (t.parent != null) {

            if (t.parent.lChild == t) {
                returnTree = t.parent.lChild;
                t.parent.lChild = null;
            } else {
                returnTree = t.parent.rChild;
                t.parent.rChild = null;
            }
        } else {
            returnTree = root;
            root = null;

        }

    } else if (t.lChild == null) {
        t = t.rChild;
    } else if (t.rChild == null) {
        t = t.lChild;
    } else {
        temp = t.lChild;
        while (t.rChild != null) {
            temp = temp.rChild;
        }
        t.data = temp.data;
        BST_Delete(t.lChild, temp.data);
    }
    return returnTree;
}