Удаление узла из дерева двоичного поиска (BTS) и метод-преемник

Question

В моем новом назначении классов один из классов в моей программе, который я должен написать, - это класс BinarySearchTree. Есть 2 метода, с которыми я немного борюсь, это метод remove и метод successor.

Бинарное дерево поиска хранит данные только во внутренних узлах, поэтому конечные узлы пусты, но не равны нулю. однако в моем методе remove я всегда получаю nullPointerException при if(parent.getLeft() == nodeToBeRemoved), и я не уверен почему.

Вот мой код для remove метода:

public void remove(Pair k) throws DictionaryException {
    BinaryNode nodeToBeRemoved = searchTreeNode(root, k); //Searches the tree for the node to be removed.
    if(nodeToBeRemoved.isLeaf()) { //If the search returns a leaf node, the node to be removed is not in the tree.
        throw new DictionaryException("key");
    } else {
        //If the node to be removed has one child (plus one leaf child) or both children are leaf nodes.
        if(nodeToBeRemoved.getLeft().isLeaf() || nodeToBeRemoved.getRight().isLeaf()) {
            BinaryNode childNode;
            if(nodeToBeRemoved.getLeft().isLeaf()) {
                childNode = nodeToBeRemoved.getRight();
            } else {
                childNode = nodeToBeRemoved.getLeft();
            }
            BinaryNode parent = nodeToBeRemoved.getParent(); //Parent of the node to be removed.
            if(nodeToBeRemoved == root) { //If the node to be removed is the root, the child is set to be the new root.
                root = childNode;
            } else {
                if(parent.getLeft() == nodeToBeRemoved) {
                    parent.setLeft(childNode);
                } else {
                    parent.setRight(childNode);
                }
            }
        } else { //If the node to be removed has two children (non leaf children).
            BinaryNode successorNode = smallestNode(nodeToBeRemoved.getRight()); //Finds the successor node of the node to be removed.
            nodeToBeRemoved.setData(successorNode.getData()); //Sets the node to be removed data to be the successor node's data.
            remove(successorNode.getData().getKey()); //The successor is then removed.
        }
    }
}

и мой put метод, если на самом деле что-то не так с этим:

public void put(Record r) throws DictionaryException {
    BinaryNode newNode = searchTreeNode(root, r.getKey()); //Searches the tree for the node.
    if(!newNode.isLeaf()) { //If the node is not a leaf, then the data is already in the tree, so exception is thrown.
        throw new DictionaryException("key");
    } else { //Otherwise, the data item is not in the tree, and will be added.
        newNode.setData(r);
        newNode.setLeft(new BinaryNode()); //Sets the left child to be a leaf node.
        newNode.setRight(new BinaryNode()); //Sets the right child to be a leaf node.
    }
}

Метод-преемник принимает ключ "k" и возвращает данные, сохраненные в узле-преемнике, однако ключ "k" уже не нужно хранить ни в одном из узлов дерева, поэтому то, что я сделал, было временно добавил его в дерево, нашел узел-преемник и затем удалил его, используя метод remove. Однако, используя файл test.java, который я получил от prof, этот метод не проходит тест. Вот мой код преемника:

public Record successor(Pair k) {
    boolean added = false; //A boolean variable to determine if the key is added to the tree.
    BinaryNode tempNode = root;
    //If the key is not in any of the nodes in the tree, then add this node to the tree.
    if(searchTreeNode(tempNode, k).isLeaf()) {
        put(new Record(k, null));
        added = true; //sets added to true, showing that the node with "key" was added.
    }
    BinaryNode inputNode = searchTreeNode(tempNode, k);
    //If the right child of the node is not null, then the successor is the smallest node in the right subtree.
    if(!inputNode.getRight().isLeaf()) {
        return smallestNode(inputNode.getRight()).getData();
    }
    //Otherwise, we have to search up the tree until the parent of the node is the left child of another node. then
    //That "another node" will be the first right ancestor, which is the successor node.
    BinaryNode inputNodeParent = inputNode.getParent();
    while(inputNodeParent != null && inputNode == inputNodeParent.getRight()) {
        inputNode = inputNodeParent;
        inputNodeParent = inputNodeParent.getParent();
    }

    Record dataValue = inputNodeParent.getData();

    //If the key is added to the tree, we need to remove it now, since it was not originally in the tree.
    if(added == true) {
        remove(k);
        added = false;
    }

    return dataValue;
}

И метод searchTreeNode, используемый в put и remove:

private BinaryNode searchTreeNode(BinaryNode r, Pair k) {
    BinaryNode tempNode = r; //duplicates the root node.
    BinaryNode prev = r.getParent();
    if(tempNode.isLeaf()) {
        return tempNode;
    } else {
        if(tempNode.getData().getKey().compareTo(k) == 0) {
            return tempNode;
        } else if(tempNode.getData().getKey().compareTo(k) == 1) {
            return searchTreeNode(tempNode.getLeft(), k);
        } else {
            return searchTreeNode(tempNode.getRight(), k);
        }
    }
}

Я действительно не знаю, почему я получаю ошибку nullPointerException в методе remove, и не совсем уверен, почему метод successor тоже не работает.

Редактировать

Код для BinaryNode getParent метода вместе с конструктором:

public BinaryNode(Record value, BinaryNode left, BinaryNode right, BinaryNode parent) {
    recordValue = value; //Initializes the Record object.
    leftNode = left; //Initializes the left child of this node.
    rightNode = right; //Initializes the right child of this node.
    parentNode = parent; //Initializes the parent of this node.
}
public BinaryNode() {
    //Initializes all the variable to null.
    recordValue = null;
    leftNode = null;
    rightNode = null;
    parentNode = null;
}
public BinaryNode getParent() {
    return parentNode;
}