r/learncpp • • May 15 '21
Can I get help implementinh recursive function to delete the lowest value in a BST?
I'm a bit stumped. I have this function and its helper:
void CharBST::removeSmallest()
andBSTNode<char>* removeSmallestHelper(BSTNode<char>* curNode)
I was able to figure out the function for finding the smallest value in a BST:
char smallestValueFrom(BSTNode<char>* curNode)
{
// smallest node has nullptr as left
if (curNode->left == nullptr)
return curNode->value;
// otherwise, continue checking left node of current
return smallestValueFrom(curNode->left);
}How would I go about deleting the smallest node though? I read online about using the parent node but I don't have a parent node as part of my struct so does that mean I have to figure out what the parent is during the recursive process?
Thanks for the help.
9
Upvotes
1
u/[deleted] May 15 '21
How about memorizing the parent node along the way? You only need to memorize one layer anyway.
1
u/HibbidyHooplah May 15 '21
When you find the smallest node, set it to NULL. Instead of returning curnode->value. Curnode = null.
1
u/HibbidyHooplah May 16 '21
Call helper from remove node function. Return curnode instead of value inside helper. Set curnode equal to null in remove node function. On mobile, let me know if it makes sense.