I WAS NOT ABLE TO UNDERSTAND THE CASE 3 WHERE WE HAVE TO DELETE NODE WITH 2 CHILDREN AND HOW IT WILL RECURSIVELY CALL THE FUNCTION?
Cpp-bst-deletion
Hello @itsexp_2302,
Let’s understand that case i.e. case 3 where the node to delete has two children.
STEPS:
-
Go to the node with the value that is just greater than the value of the node that is to be deleted present in the BST.
a) first go to the right child of the node to be deleted.
b) then keep going to the left child until there is no more left child.
c) This node will contain the required value
Example:
Suppose, we have to delete node with value 5 and the value just greater than this value is 7 in the BST.
___________________1
___________2 _______________5
_____________________4 ___________9
_____________________________7 _______10
________________________________8 -
Replace the value of node to be deleted with the value of the node having just greater value i.e. 7 in this example.
___________________1
___________2 _______________7
_____________________4 ___________9
_____________________________7 _______10
________________________________8 -
As, the value of the node to be deleted is no more there. So, just delete the node with the value same as of that node that needed to be deleted earlier i.e. node whose actual value was 7.
Now, this will become either Case of no child or now child.
In this example, it is the case of one child.
a) make a recursive call with root as root->right and key=root->data
b) It will recursively delete the node.
___________________1
___________2 _______________5
_____________________4 ___________9
_____________________________8 _______10
Hope, this would help.
Give a like if you are satisfied.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.