Stack overflow error while deleting BST node in C

Question

I'm currently running into a problem that I can't seem to figure out. The goal is to try to delete a node from a binary search tree. For some reason I keep running into a stack overflow because of this function. Is there something that I'm missing?

int delete(struct node * n,int value) {
//if there is no bst 
if (n == NULL || head == NULL) {
    return 0;
}

//if head node is the node that has to be deleted
if (head->value == value) {
    if (head->left != NULL && head->right == NULL) {
        head = head->left;
    } else if (head->left == NULL && head->right != NULL) {
        head = head->right;
    } else if (head->left != NULL && head->right != NULL) {
        int temp = leftOfRight(head);
        head->value = temp;
        delete(head->right,temp);
    } else {
        head = NULL;
    }
}

if (n->left != NULL && n->left->value == value) { //if left node is the one that has to be deleted
    if (n->left->left != NULL && n->left->right != NULL) {
        int temp = leftOfRight(n->left);
        n->value = temp;
        delete(n->right,temp);
    } else if (n->left->left != NULL) {
        n->left = n->left->left;
    } else if (n->left->right != NULL) {
        n->right = n->right->right;
    } else {
        n->left = NULL;
    }
} else if (n->right != NULL && n->right->value == value) {
    if (n->right->left != NULL && n->right->right != NULL) { //if right node is that one that has to be deleted
        int temp = leftOfRight(n->right);
        n->value = temp;
        delete(n->right,temp);
    } else if (n->right->left != NULL) {
        n->right = n->right->left;
    } else if (n->right->right != NULL) {
        n->right = n->right->right;
    } else {
        n->right = NULL;
    }
} else if (value < n->value) {
    return delete(n->left,value);
} else if (value > n->value) {
    return delete(n->right,value);
}
return 1; }

Have you put a debugger on it? A debugger is always my first tool in cases where the program reliably fails. — Mobius, Oct 02 '17 at 03:06
Refer to this : https://www.youtube.com/watch?v=gcULXE7ViZw&t=1s — Sourav Gulati, Oct 02 '17 at 03:07
You are not freeing your node in delete . So whether n->left or n->right it is pointing to some live memory location but not null so the condition may always become true and keep calling the delete recursively causing to stackoverflow. LeftOfRight function code should also be posted here :) — 0decimal0, Oct 02 '17 at 06:23
Please [edit] your question to show us what kind of debugging you've done. I expect you have run your [mcve] within Valgrind or a similar checker, and to have investigated with a debugger such as GDB, for example. Ensure you've enabled a full set of compiler warnings, too. What did the tools tell you, and what information are they missing? And read Eric Lippert's [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). — Toby Speight, Oct 02 '17 at 09:35

C Thomas · Answer 1 · 2017-10-02T12:02:32.217

The main problem is that you aren't setting your pointers to nullptr after calling delete. This leads to undefined behaviour.

Let me demonstrate:

//Create ptr & set to nullptr
Node* p_node = nullptr;
std::cout << "ptr: " << p_node << std::endl;

//Create new node on heap and point to it
Node* n = new Node(11);
p_node = n;
std::cout << "ptr: " << p_node << " node val: " << p_node->value << std::endl;

//Delete pointed-to object 
delete p_node;
std::cout << "ptr: " << p_node << " node val: " << p_node->value << std::endl;

//Set both ptrs back to nullptr
p_node = nullptr;
n = nullptr;
std::cout << "ptr: " << p_node << std::endl;

output:

ptr: 0
ptr: 0x8c7de0 node val: 11
ptr: 0x8c7de0 node val: 3504064
ptr: 0

Delete does not delete the pointer, but calls the destructor of the pointed-to object and deallocates the memory. After this we'll be accessing random memory.

A couple of other points:

It's hard to know the whole context, but your method of traversing the tree seems a little confusing. Most BST implementations use a while loop with a Node* current which you use to traverse the list recursively until it lands on the value to be deleted, or becomes nullptr - while (current != nullptr) ... if (current->value == value) break; then you check if the node has 0,1 or 2 children - and act accordingly. It's much simpler to read that way. If you wanted to abstract it you could write a find_node function that simply returns a ptr to a found node.
Use nullptr rather than NULL.

Stack overflow error while deleting BST node in C

1 Answers1