Удаление BinaryTreeNode из BinaryTree

У меня есть BinarySearchTree , которое состоит из узлов, которые являются одновременно классом шаблона для dataType student, где student - это класс с частными переменными имени и оценки.

На данный момент я могу распечатать дерево, найти в нем имена и / или оценки, но у меня возникают проблемы с удалением узлов из дерева.

Я пытаюсь удалить всех учащихся с оценкой <50 (так не удалось).

После удаления узла должно произойти одно из следующего:

1. Левый дочерний элемент пуст: заменить узел его правым дочерним элементом.
2. Левый дочерний элемент не пуст: замените узел на самый высокий элемент в левой ветви .

Насколько я понимаю, если бы это было дерево:

      1
     /  \
    2    3
   / \   /\
  4  5  6  7

Если бы 2 не удалось, т.е. имело оценку <50

, вы бы получили

     1
    /  \
  4     3
   \    / \
    5  6  7

4, являющийся наивысшим элементом в левой ветви.

Если бы это было дерево:

     1
    /  \
   2     3
   \     / \
    5  6   7

и 2 неуспешных

, вы бы получили

     1
    /  \
  5      3
        /  \
       6   7

Если бы это было дерево:

     1
    /  \
  2     3
 / \    / \
 4  5  6  7

и 1 не удалось

, вы бы получили

     5
    /  \
  2     3
 /      / \
4      6  7

I у меня было много проблем, пытаясь создать функции для этого, на данный момент у меня есть:

void checkBranch()  //called from main - used to pass the root node to checkBranch()
{
checkBranch(studentTree.getRoot());
}

bool checkBranch(BTNode<Student>* currentNode)
{
if (currentNode != NULL)
{
    if (checkBranch(currentNode -> getLeft()))
    {
        deleteNode(currentNode, true);
    }  

    if (checkBranch(currentNode -> getRight()))
    {
        deleteNode(currentNode, false);
    }

    return (currentNode -> getData().getGrade() < 50.0);
}

else
{
    return false;
}
}

Теперь я пытаюсь добавить функцию deleteNode , где я просто застрял в том, что делать / обрабатывать что должно произойти:

void deleteNode(BTNode<Student> *parentNode, bool left)
{
BTNode<Student>* nodeToDelete;

if (left)
{
    nodeToDelete = parentNode->getLeft();
}
}