Deletion from binary search trees

We have three cases when deleting a node from a binary search tree:

• ·      If we are trying to delete a leaf , its simple we just remove it from the tree and the property of the BST is not violated.
• ·      If we are trying to delete a node that has one subtree, we connect its parent directly to its only subtree. In the following example we are trying to delete 3 and it has only one subtree:

•      The last case is when we have two subtrees; we follow this technique we leave the node that we want to delete and rather remove its value and search for another value that can be replaced their (without violating the BST property of course ) and then we delete the node that had the new value. For example:

       If we wish to delete the 6 in the following tree --------> we delete its value but keep       the actual node.

So the hint to finding the new value is one of two options its either the largest value in the left subtree or the smallest in the right subtree. Below is an illustration of how we replaced the value 3 and deleted the actual node.