Tree insert / remove / print crashes

Question

I'm trying to implement a tree from an hpp file and I seem to be running into issues with the delete functionality. The logic I am following makes sense, however I cannot seem to figure out why it crashes when I print something out after removing an object.

Tree::Tree() {
    root=NULL;
}

void Tree::print() const {
    printinOrder(root);
}

void Tree::printinOrder(Tree::Node* root) const {
    if (root == NULL) return;
    printinOrder(root->left);
    cout<<root->val<<",";
    printinOrder(root->right);
}

Tree::Node::Node(DataType value) {
    left = NULL;
    right = NULL;
    val = value;
}

bool Tree::tree_ins(Tree::Node* node, Tree::Node* insert_node) {
    if (node-> val == insert_node->val) return false;
    if (insert_node->val > node->val && node-> right == NULL) {
        node->right = insert_node;
        return true;
    }
    if (insert_node->val < node->val && node-> left == NULL) {
        node->left = insert_node;
        return true;
    }
    if (insert_node->val > node->val) return tree_ins(node->right, insert_node);
    if (insert_node->val < node->val) return tree_ins(node->left, insert_node);
}

bool Tree::insert(int val) {
    if (root == NULL) {
        root = new Node(val);
        return true;
    }
    Node* insert_node = new Node(val);
    return tree_ins (root, insert_node);
}

Tree::Node* Tree::getMinValue(Tree::Node* node) {
    if (node->left == NULL) {
        return node;
    }
    return getMinValue(node->left);
}

bool Tree::tree_rem(Tree::Node* test_node, int value) {
    if (test_node == NULL) return false;
    else if (value < test_node-> val) tree_rem (test_node-> left, value);
    else if (value > test_node-> val) tree_rem (test_node-> right, value);
    else {
        if (test_node-> left==NULL && test_node->right == NULL) {
            delete (test_node);
            return true;
        }
        else if (test_node-> left==NULL) {
            test_node->val = (test_node->right)->val;
            test_node = test_node ->right;
            test_node=NULL;
            return true;
        }
        else if (test_node-> right==NULL) {
            test_node->val = (test_node->left)->val;
            test_node = test_node ->left;
            test_node=NULL;
            return true;
        } else {
            Node* minNode = getMinValue(test_node->right);
            test_node->val = minNode->val;
            tree_rem(test_node->right, minNode->val);
            return true;
        }
    }
}

bool Tree::remove(int val) {
    if (root == NULL) {
        return false;
    }
    Node* temp = root;
    return tree_rem (temp, val);
}

Insertion works, printing the tree works. I noticed that after removing an object printing the tree crashes the program, however if I insert something right after removing an object, and then print the tree, it does not crash (but inserts it into the wrong location)

If I run it in this sequence, it crashes:

bst->insert(5);
bst->insert(3);
bst->insert(7);
bst->remove(7);
bst->print();

Suggested reading: [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) — Borgleader, Dec 09 '18 at 23:46

Dmytro Dadyka · Accepted Answer · 2018-12-10T09:09:53.763

3

If you change a pointer value, it must be passed by reference, so:

bool Tree::tree_rem(Tree::Node*& test_node, int value)

In your code, all actions on the test_node pointer have an effect only inside function, you work with a copy of test_node, so test_node = test_node->right; really does nothing with passed argument.

Also, you need to set test_node pointer to NULL after deleting.

 if (test_node->left == NULL && test_node->right == NULL) {
            delete (test_node);
            test_node = NULL;
            return true;
         }

edited Dec 10 '18 at 09:09

answered Dec 10 '18 at 00:00

Dmytro Dadyka

2,208
5
18
31

Tried this, it did not work. I'm already passing a pointer to the function though. – user2883071 Dec 10 '18 at 02:12
user2883071, try `test_node = NULL;` fix. – Dmytro Dadyka Dec 10 '18 at 09:11
That fixed it. thank you Dymtro. 2 questions. Since I am passing a pointer value in, why do I have to pass by reference? even if it creates a copy of the pointer value, doesn't that point to the same memory location as root? Second, why should I be setting `test_node` to NULL after? doesn't delete free up the memory and make it available (as opposed to `free()`? – user2883071 Dec 10 '18 at 12:38
1. This quation explained here https://stackoverflow.com/questions/10240161/reason-to-pass-a-pointer-by-reference-in-c 2. Becouse you use checking for null in your `printinOrder` : `if (root == NULL) return;`. This check will not work if you do not set NULL manualy. `delete` doesn't do it automatically. – Dmytro Dadyka Dec 10 '18 at 12:50

Tree insert / remove / print crashes

1 Answers1