BST Deletion doubt

#1

Hi! i was going through the BST deletion. when we delete a node with 2 children, after replacing the root node with the inorder successor, when we delete the successor from the subtree, shouldn’t it be root->right = DeleteInBst(root->left, replace->data) because we picked the node to be replaced from the left subtree of the right subtree.

#2

See this

          50                            60
       /     \         delete(50)      /   \
      40      70       --------->    40    70 
             /  \                            \ 
            60   80                           80

if we delete 50 having 2 child first we find inorder successor in right sub tree which is 60[first by going at 70 then till left->null ], after that we will delete by calling recursive function only.
So this is not right

it should be
DeleteInBst(root->right, replace->data) because root is at 60 after updating value.

#3

i know that the root is 60 after updating the value. what i am saying is in order to delete 60 from the subtree, shouldn’t we traverse in the left branches of the right subtree because we got 60 from the left subtree of 70

#4

if root is 60, and you have to find 60 in your right sub tree from root node, then it should be this only right ?

root->right is 70 , replace data is 60
from here bst calls will be made to search 60. Got it?

#5

when we traverse on right subtree of 60, we take 70 as root node [deleteInBST(root->right, replce->data)] and due to recursion, we’ll get to 80 because of ‘root->right’ in the function call and not 60.

#6

See this

            //Find inorder sucessor from right tree

			node*replace=root->right;   //(replace is 70, before updation and root is 50)

			//Find minimum element in right tree
            while(replace->left!=NULL)
            {
                replace=replace->left;		
            }
            //replace is having a value of 60

           //store the value of replace data into root which was 50

            root->data=replace->data; // so 50 equals to 60 after updating
           
 
           //delete the value of replace node from tree to avoid duplicates(replace->data = 60)
            root->right=deleteInBst(root->right,replace->data); 
           //root right here is 70 and replace data is 60
            return root;

Hope now you will get it.

#7

i get the whole thing, my doubt is in the part where we traverse the right subtree to remove the duplicate. I am saying that when we have 70 as root node, from 70, shouldn’t we traverse the left subtree because 60 was in the left subtree of 70.

#8

Yes this one is right.

#9

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.