Deletion in binary search tree

A simple way of delete a node from binary search tree
with the help of an example
Three possible cases also described in these slides
If any question about these slides then please ask in comments

1. Deletion

* Deletion is simple if we are deleting a leaf
node

+ Three cases

pd

LeopardROtk

2. Deletion

+ If the element to be deletedis a leaf node

yo
7
q 1

LeopärdRrök

3. Deletion

+ If the element to be deleted has one child

\

4. Deletion

+ If the element to be deleted has one child

@ (3) de
>
14]

ff

LeopärdRöck

5. Deletion

+ If the element to be deleted has both children

y

)

x
Le

6. Deletion

+ If the element to be deleted has both children

EN
»
e O \ á

4

LeoparoReck

7. Code

struct BSTNode* Delete(struct BSTNode *root, int data)

{

struct BSTNode *temp;

if(root==NULL)
printf(“No such element exists”);

else if(data<root->data)
root->left=Delete(root->left,data);

else if(data> root->data)
root->right=Delete(root->right,data);

8. Clipboard Image Tools Brushes) Shapes Size

struct BSTNode* Delete(stri

{

|

struct BSTNode *temp; 0

if(root==NULL) | | ©)
printf(“No such elem |

else if(data<root->data) |
root->left=Delete(roo||

else if(data> root->data)

root->right=Delete(r

9. Code

else { //element found

if{root->left && root->right) { //both children
temp=FindMax(root->left);
root->data=temp->data;

root->left=Delete(root->left,root->data);

}
else{ //one or none child
temp=root;
if(root->left==NULL)
root=root->right;
if(root->right==NULL)
root=root->left;
free(temp);
}
} //end of else
return(root);

} //end of function

10. où

== an M