## 2.1. Deleting a Node From a Binary Search Tree

Of course, if we are trying to delete a leaf, there is no problem. We
just delete it and the rest of the tree is exactly as it was, so it is
still a BST.
There is another simple situation: suppose the node we're deleting
has only one subtree. In the following example, `3' has only 1
subtree.

To delete a node with 1 subtree, we just `link past' the node, i.e.
connect the parent of the node directly to the node's only subtree.
This always works, whether the one subtree is on the left or on the
right. Deleting `3' gives us:

which we normally draw:

Finally, let us consider the only remaining case: how to delete a node
having two subtrees. For example, how to delete `6'? We'd like to do
this with minimum amount of work and disruption to the structure of
the tree.

The standard solution is based on this idea: we leave the node
containing `6' exactly where it is, but we get rid of the value 6 and
find another value to store in the `6' node. This value is taken from
a node below the `6's node, and it is *that* node that is
actually removed from the tree.

So, here is the plan. Starting with:

Erase 6, but keep its node:

Now, what value can we move into the vacated node and have a binary
search tree? Well, here's how to figure it out. If we choose value X,
then:
- everything in the left subtree must be smaller than X.
- everything in the right subtree must be bigger than X.

Let's suppose we're going to get X from the left subtree. (2) is
guaranteed because everything in the left subtree is smaller than
everything in the right subtree. What about (1)? If X is coming from
the left subtree, (1) says that there is a unique choice for X - we
must choose X to be the largest value in the left subtree. In our
example, 3 is the largest value in the left subtree. So if we put 3 in
the vacated node and delete it from its current position we will have
a BST with 6 deleted.

Here it is:

So our general algorithm is: to delete N, if it has two subtrees,
replace the value in N with the largest value in its left subtree and
then delete the node with the largest value from its left subtree.
**Note:**
The largest value in the left subtree will never have two subtrees.
Why? Because if it's the largest value it cannot have a *right*
subtree.

Finally, there is nothing special about the left subtree. We could do
the same thing with the right subtree: just use the *smallest*
value in the right subtree.