#BST why does remove call on Line 74 work?

19 messages · Page 1 of 1 (latest)

dense burrow
#

Why does the remove call work on line 74? To my understanding this is just a recursive call in the function. If I wanted to name the function “pizza” instead of “remove” then I could have done so. So why does this remove call work? To my understanding this function takes in 2 arguments (a value and a parent node) but nowhere is it coded a deletion of the node. So why does this line successfully delete the desired node?

Image_9-7-22_at_11.01_PM.jpg
robust bloomBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For more information use !howto ask.

tawny robin
#

pizza?

granite tapir
#

I need to see the resultant assembly

cobalt chasm
#

is there more code to the method?

#

this doesn't yet contain the actual deletion

#

it just traverses around

#

i suspect the actual deletion happens in a line below that u didn't share yet

#

often by just skipping the node

#

i. e. removing linkage to the tree

#

that said, the only way to understand complex code like that is by grabbing pen and paper with some simple example

#

and then step through the code and draw a picture of the example

#

to illustrate what's going on

#

those traversal lines modify the tree heavily by moving around nodes

dense burrow
# cobalt chasm often by just skipping the node

Yes! Often times by just skipping the node. Connecting the “currentNode” to its next next value would essentially delete the node. That is my understanding, which is why I am confused to see the remove function called. Maybe there is something I am missing? But here is the rest of the deletion code along with the getMinValue helper function

#

BST &remove(int val, BST *parentNode = nullptr) {
BST *currentNode = this;
while(currentNode != nullptr){
if (val < currentNode -> value){
parentNode = currentNode;
currentNode = currentNode -> left;
} else if (val > currentNode -> value){
parentNode = currentNode;
currentNode = currentNode -> right;
} else{
if (currentNode -> left != nullptr && currentNode -> != nullptr){
currentNode -> value = currentNode -> right ->getMinValue();
currentNode -> right -> remove(currentNode-> value, currentNode);
} else if (parentNode = nullptr){
if (currentNode -> left != nullptr){
currentNode -> value = currentNode->left ->value;
currentNode -> right = currentNode -> left -> right;
currentNode -> left = currentNode ->left -> left;
} else if (currentNode -> right != nullptr){
currentNode -> value = currentNode -> right -> value;
currentNode -> left = currentNode -> right -> left;
currentNode -> right = currentNode -> right -> right;
}else {
// this is a single-node tree; do nothing.
}
else if (parentNode -> left == currentNode){
parentNode -> left = currentNode -> left != nullptr ? currentNode -> left: currentNode->right;
} else if (parentNode -> right == currentNode){
parentNode->right = currentNode->lleft != nullptr ? currentNode->left : currentNode->right;
}
break
}
}
return *this;
}
int getMinValue(){
if (left == nullptr){
return value;
} else {
return left ->getMinValue();
}
}

dense burrow
dense burrow
# tawny robin pizza?

I said pizza just to say that I could have named the function anything, which is why I did not understand a function named “remove” with no remove implementation removed a node. I did not mean to throw you off

robust bloomBOT
#

This question thread is being automatically closed. If your question is not answered feel free to bump the post or re-ask. Take a look at !howto ask for tips on improving your question.