Delete a Node from C++ Binary Search Tree (class not struct)

Question

I'm trying to manage a BST in C++ for my academic purpose.

I'm not having problems anywhere except for the DeleteNode function, also I chose to implement this data structure with a class and not with a struct.

The problem is, that I cant figure it out how to make properly work the delete function, often I got 0xDDDDDDDDD error my debugger say, sometimes I can delete the node, sometimes my program crash.

I think that's a possible problem of pointer, but I just can't figure it out where I'm doing wrong.

Here's my delete node function, the one I'm getting serious trouble about:

EDIT: The no-son delete case works perfectly, the one i'm getting mad about is the one-son-case delete.

 //function that delete a selected node
    void DeleteNode(TreeNode* root,int key) {
        /*we got three case here:*/


        //until we find the right node with value in the tree
        if (root->getValue() != key && root != nullptr) {
            if (root->getValue() > key) {
                DeleteNode(root->Left, key);
            }
            else if (root->getValue() < key) {
                DeleteNode(root->Right, key);
            }
        }
        else { //when we found the right node, then operate 
               /* THIS WORKS PERFECTLY! */

            //first case: our node got no right and left son
            if (!root->Left && !root->Right) {

                TreeNode* tmp = root->Father; 

                if (tmp->Left == root) { //if the son is a left son
                    tmp->Left = nullptr;
                    delete root;
                }
                else if (tmp->Right == root) { //if the son is a right son
                    tmp->Right = nullptr;
                    delete root;
                }

            }
            //second case: our node got a left but no right son
            /* THIS ONE DOESN'T WORK. */
            else if (!root->Right) { 
                TreeNode *tmp = root;
                root = root->Left; //new root is the left son of the root
                root->Father = tmp->Father; //linking the father to the new son
                tmp->Father->Left = root; //linking the son to the new father

                delete tmp;                     

                std::cout << "Erased!" << std::endl;
            }
            else if (!root->Left) {
                TreeNode *tmp = root;
                root = root->Right; //new root is the right son of the root
                root->Father = tmp->Father; //linking the father to the new son
                tmp->Father->Right = root; //linking the son to the new father

                delete tmp;

                std::cout << "Erased!" << std::endl;

            }
        }


        }

I tried a lot of combination, but the result are the same every time: it crashes on the first occurrence of the InOrder display function. (and when it does not, the function just delete the first nodes and then crash when i try to delete a new one.)

Here's a simple main where i'm trying to act the delete:

int main()
{

    TreeNode root;

    root.insertNode(&root,50);
    root.insertNode(&root,30);
    root.insertNode(&root,20);
    root.insertNode(&root,40);
    root.insertNode(&root,70);
    root.insertNode(&root,60);
    root.insertNode(&root,80);

    for (int i = 0; i < 5; i++) {
        int n;
        cin >> n;

        root.DeleteNode(&root, n);

        cout << "In-Order: "; root.inOrder(&root);
        cout << endl;
        cout << "Pre-Order: "; root.preOrder(&root);
        cout << endl;
        cout << "Post-Order: "; root.postOrder(&root);
        cout << endl;
    }

}

Here's my full BST code (except the delete one that i submitted before, just for being more complete in the understanding of my code)

    class TreeNode {
private:
    int value;
    TreeNode* Left;
    TreeNode* Right;
    TreeNode* Father;

public:

    //constructor
    TreeNode() {
        this->Right = nullptr;
        this->Left = nullptr;
        this->Father = nullptr;
    }

    TreeNode(int value) {
        this->value = value;
        this->Right = nullptr;
        this->Left = nullptr;
        this->Father = nullptr;
    }

    //functions
    int getValue() { return value; }
    void setValue(int value) { this->value = value; }


    //function to create a new node and insert a value into it
    TreeNode* insertNode(TreeNode* root, int value) {

        if (root->getValue() == NULL) {
            root->setValue(value);
            root->Father = nullptr;
        }

        else {
            if (value > root->getValue()) {
                if (root->Right) {
                    insertNode(root->Right, value);
                }
                else
                    root->Right = new TreeNode(value);
                    root->Right->Father = root;
            }
            else if (value < root->getValue()) {
                if (root->Left) {
                    insertNode(root->Left, value);
                }
                else
                    root->Left = new TreeNode(value);
                    root->Left->Father = root;
            }

        }
        return root;
    }

    //function to search a value into a BST
    TreeNode* SearchNode(TreeNode* root, int key) {

        if (root->getValue() == key) {
            return root;
        }
        else if (root->getValue() < key) {
            if (root->Right) {
                SearchNode(root->Right, key);
            }
            else return nullptr;
        }
        else if (root->getValue() > key) {
            if (root->Left) {
                SearchNode(root->Left, key);
            }
            else return nullptr;
        }
    }

    //function that return the height of the tree 
    int TreeHeigth(TreeNode* root) {

        int heigth;

        if (root == nullptr) {
            return 0;
        }
        else {
            return heigth = 1 + max(TreeHeigth(root->Left), TreeHeigth(root->Right));
        }
    }

    //function that returns the number of the nodes
    int CountTreeNode(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        else {
            return CountTreeNode(root->Left) + CountTreeNode(root->Right) + 1;
        }
    }

    //function that returns the minimum values into the tree
    TreeNode* MinimumNode(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }

        while (root->Left != nullptr) {
            root = root->Left;
        }

        return root;
    }

    //function that returns the maximum value into the tree  
    TreeNode* MaximumNode(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }

        while (root->Right != nullptr) {
            root = root->Right;
        }

        return root;
    }

    //function that returns a successor of a given nodeb
    TreeNode* SuccessorNode(TreeNode* node) {

        //first case: our node got a rigth subtree:
        if (node->Right != nullptr) {
            return MinimumNode(node->Right); 
        }

        //second case: our node doesnt got a right subtree: lets get 
        //upper in the tree until our node isn't a left child.

        TreeNode* Ancestor = node->Father;

        while (Ancestor != nullptr && node == Ancestor->Right) {
            node = Ancestor;
            Ancestor = Ancestor->Father;
        }

    }

    //function tht returns a predecessor of a given node
    TreeNode* PredecessorNode(TreeNode* node) {

        //first case: (inverse to successor) our node got a left subtree:
        if (node->Left != nullptr) {
            return MaximumNode(node->Left);
        }

        TreeNode* Ancestor;

            if (node->Father == nullptr)
                return nullptr;
            else 
                Ancestor = node->Father;

        while (Ancestor != nullptr && node == Ancestor->Left) {
            node = Ancestor;
            Ancestor = Ancestor->Father;
        }

        return Ancestor;
    }



    //function that prints information about nodes
    void InfoNode(TreeNode *root) {

        root != nullptr ? std::cout << "Nodo corrente: " << root->getValue() << std::endl
            : std::cout << "Nodo corrente: " << "NULL" << std::endl;

        root->Father != nullptr? std::cout << "Padre: " << root->Father->getValue() << std::endl
            : std::cout << "Padre: " << "NULL" << std::endl;

        root->Left != nullptr ? std::cout << "Figlio SX: " << root->Left->getValue() << std::endl
            : std::cout << "Figlio SX: " << "NULL" << std::endl;

        root->Right!= nullptr ? std::cout << "Figlio DX: " << (root->Right)->getValue() << std::endl
            : std::cout << "Figlio DX: " << "NULL" << std::endl;
    }

    //visits of a tree
    void preOrder(TreeNode* root) {
        if (root != nullptr) {
            std::cout << root->getValue() << " ";
            preOrder(root->Left);
            preOrder(root->Right);
        }
    }

    void inOrder(TreeNode* root) {
        if (root != nullptr) {
            inOrder(root->Left);
            std::cout << root->getValue() << " ";
            inOrder(root->Right);
        }

    }

    void postOrder(TreeNode *root) {
        if (root != nullptr) {
            postOrder(root->Left);
            postOrder(root->Right);
            std::cout << root->getValue() << " ";
        }
    }


    //max between 2 numbers
    int max(int a, int b) {
        return a > b ? a : b;
    }


    };

And there's the representation of the tree I'm trying to work on:

          50
       /     \
      30      70
     /  \    /  \
   20   40  60   80 

Where i'm doing it wrong?

Answer 1

I would like to add something to the answer of @Bonje Fir. Sure it is a correct answer, but partially: I'll explain why.

He suggested to swap the last piece of code i wrote:

Case: we're in the right subtree, and we would like to erase 70 (because we don't have anymore the leaf node 60):

          50
       /     \
      30      70
     /  \       \
   20   40      80 

now, with the code that @Bonje Fir suggested us, we would got a problem here:

TreeNode *tmp = root;
root = root->Right; //new root is the right son of the root
root->Father = tmp->Father; //linking the father to the new son
tmp->Father->Left (instead of Right)  = root; //linking the son to the new father

Because the code is saying, that once you updated the new root with his son, link the father of the previous root (that we saved in a tmp variable) with his left son. Then we would assist to something like this:

          50
       /     x
      80      80
     /  \       
   20   40     

and that's inconsistent.

Now take a look on the other side, with the same code and without leaf node 20:

      50
   /      \
  30       70
    \     /  \
    40   60  80

the code fit here, because we're in the right subtree. so once update 30 with 40 (root = root -> right) the situation would be this:

      50
   x      \
  40       70
          /  \
         60  80

then the piece of code @Bonje Fir wrote us, would fit perfectly:

tmp->Father->Left = root

because for sure, we're assigning 40 to the left son of the father of the original root. (because we're in the left subtree.)

      50
   /      \
  40       70
          /  \
         60  80

So i made a little change to correct this logic problem, and make it work both in the right and left subtree.

else if (!root->Left) {
            TreeNode *tmp = root;
            root = tmp->Right;
            root->Father = tmp->Father; //linking the father to the new son

            //we need also to connect the son with the father, but first
            //we need to know in which subtree we're in.

            if (root->Father->Right == tmp) //if we're in the right subtree
                tmp->Father->Right = root;
            else                            ////if we're in the left subtree
                tmp->Father->Left = root;

            delete tmp;

            std::cout << "Erased!" << std::endl;                
        }

i took advantage of the fact i didnt erase my root, once assigned the new one, so the father of the root still points to the old root.

(same speech for the opposite case.)

Answer 2

Look at this condition: root->getValue() != key && root != nullptr, This first calls getValue and after that checks root has legal value. swap them(root != nullptr && root->getValue() != key).

Finally I think you must change last line to tmp->Father->Left = root; to fix crash problem.

TreeNode *tmp = root;
root = root->Right; //new root is the right son of the root
root->Father = tmp->Father; //linking the father to the new son
tmp->Father->Right = root; //linking the son to the new father

PS: Also do this exchange for other side...

Note: This is true until root is left child of his father otherwise your code is true. Precisely you must check if root is left child if his father do tmp->Father->Left = root; else tmp->Father->Right = root;

Note: As you mentioned your code does not handle deletion of a node with two childern.

Answer 3

Well, once one know that DEBUG version use sentinel value, it become much more trivial to find problems in code.

• When and why will an OS initialise memory to 0xCD, 0xDD, etc. on malloc/free/new/delete?

0xDD is for dead memory. That is memory that has been already deleted. So when the debugger stop and it tells you that you have a bad pointer and the data contains a lot of 0xDD, you know the data has already been deleted. At that point, you should inspect class that contain the data to see if they are deleted too so you know which objects were deleted when the are embedded one inside another.

Be aware that sometime you might have some data that has been changed in part of the class if some operations use delete memory. Looking at memory pattern also help finding uninitialized memory and other similar problem.

Some other links:

• Why does the not allocated memory is marked like 0xCC?
• https://msdn.microsoft.com/en-us/library/974tc9t1.aspx
• https://www.codeguru.com/cpp/w-p/win32/tutorials/article.php/c9535/Inside-CRT-Debug-Heap-Management.htm
• http://www.nobugs.org/developer/win32/debug_crt_heap.html

In a case like yours, if you follow the good practice of writing unit tests, then it would even be more trivial to find the problem. In fact, if you do proper testing, then you will test all possible cases so you will know which cases fail and it would help you find where you might do something wrong.

Answer 4

As there is already an answer giving you directions to correct the specific errors, I will try to focus on a suggestion that will help you avoid similar error all together:

Try separating your current function into two:

1. One that searches a node with specific key, for example: Node* search(int key) function that returns either a pointer to the node with wanted key or nullptr, or use the one that your already have.

2. One that deletes (and re-wires) the node passed as pointer and returns: next, previous, etc: Node* delete(Node* n).

Then call search, test against nulltpr, and if different, pass the returned pointer as an input argument in delete.

In this way you could easily detect on which phase is you problem: searching or deleting.

---

P.S.: figuring out re-wiring bugs is usually done through diagrams (boxes and arrows). Decide what you should do, separate it into steps and implement it.