Deleting node in BST

[Maartin]

My Nodes structure:

struct BstNode{
    string nameValue; // Names
    vector<int> pseudoIDS; // Unique IDs
    BstNode* left;
    BstNode* right;
};

I want to implement a deletion function, that could delete whole Node by ID. For instance, I've inserted a Node: John 5 12 3 Where 5, 12, 3 are unique IDs. I would use something like DeleteById(root, 5) and it would delete whole John 5 12 3 node, because it contains ID = 5.

BstNode* DeleteById(BstNode* root, int data){
     for(unsigned int i = 0; i < root->pseudoIDS.size(); i++) {
        if(root == NULL || root->pseudoIDS.size() == 0) return root;
        if (data < root->pseudoIDS[i]) root->left = DeleteById(root->left, data);
        else if (data > root->pseudoIDS[i]) root->right = DeleteById(root->right, data);
        else // Found ya
        {
            // No child
            if(root->left == NULL && root->right == NULL){
                delete root;
                root = NULL;
                break;
             }
            // One child
            else if(root->left == NULL){
                BstNode* temp = root;
                root = root->right;
                delete temp;
                break;
             }
            else if(root->right == NULL){
                BstNode* temp = root;
                root = root->left;
                delete temp;
                break;
            }
            // Two children
            else{
                BstNode* temp = FindMin(root->right);
                root->pseudoIDS[i] = temp->pseudoIDS[i];
                root->right = DeleteById(root->right, temp->pseudoIDS[i]);
            }
        }
    }
    return root;
}

BstNode* FindMin(BstNode* root){
      while(root->left != NULL) root = root->left;
      return root;
}

int main(){
    BstNode* root = NULL; // Creating empty BST


    // TEST
    vector<int> test;
    vector<int> test2;
    vector<int> test3;

    for (int i = 0; i < 3; i++){ test.push_back(i); }
    for (int i = 10; i < 12; i++){ test2.push_back(i); }
    for (int i = 56; i < 60; i++){ test3.push_back(i); }

    root = Insert(root, "Abuels", test);
    root = Insert(root, "Caves", test2);
    root = Insert(root, "Zapes", test3);
    root = Insert (root, "Bib", test);

    // Delete

     DeleteById(root, 2);

    cout << "After deleting! " << endl;
    PrintTree(root);


    return 0;
}

Problem is simple: It doesn't delete required nodes + program crashes in weird way (it runs in compiler till the deleteById function and then says 1. main.exe has stopped working (if I delete ID with existing node) or does nothing if I delete ID with unexisting ID). I guess there's some implementation bug. I tried to run it through debugger, but didn't find any issue.

[coder777]

If root is deleted you must not continue with the loop -> a break; is required.

[Maartin]

@coder777 I edited my post based on your suggestion. Nothing changed. Did I understood it wrong?

[ne555]

> Where 5, 12, 3 are unique IDs. I would use something like DeleteById(root, 5)
> and it would delete whole John 5 12 3 node, because it contains ID = 5.
¿how do you search this kind of tree?

for(unsigned int i = 0; i < root->pseudoIDS.size(); i++) {
	if(root == NULL || root->pseudoIDS.size() == 0) return root;

if `root' is null, then you've got an invalid access in i < root->pseudoIDS.size()
if the id container is empty, you've never enter the loop.

that line is useless

[Maartin]

@ne555 Okay, but that doesn't solve the error.

[Bdanielz]

@Maartin I would suggest that you post enough code that we can compile and run to reproduce the error. This way we don't have to grasp at straws to troubleshoot your code. Also if you refactor your code to just show us the issue chances are you might actually see the problem when rewriting it for science.

[Maartin]

@Bdanielz I added more code, but I think that the DeleteById function code should be enough, as there's error in this function (if I don't call it in main, everything runs fine with-out errors). Problem is, I still can't find the error.

[Bdanielz]

Only trying to help. It looks like you intend to create your structure on the heap. As that makes the most sense for a dynamic structure. Also, it is clear that you are having issues using your delete code. So it seems you should include where you are calling 'new' as well. I suppose there are some c++ coders that can put this problem togeather with the information provided, please don't assume all of us can! :)

Also, have you stepped through this code yet? What line does it fail on specifically inside your function?

[Maartin]

@Bdanielz I see. Well, I used rubber duck debugging method, but didn't find anything. I'm pretty sure I'm setting wrong links in delete function, because compiler returns some weird memory addresses - probably links hanging "in the air" and the program crashes.

[Maartin]

Anyone?

[coder777]

One obvious problem is on line 24. On line 21 root is deleted hence you cannot use it in PrintTree(...)