# Binary Search Trees Removal

## Removing Nodes

Removing a node from a binary search tree is a bit more complicated than inserting or searching one.

If we want to remove a particular element from a tree, we must first search for the node with that value (using the searching algorithm described above). However, once we find the data we want to remove, there are three different cases.

1. The node is a leaf:

In this case, we can simply remove the node, and set the link to it to null.

2. The node has one child:

In this case, we must set the parents pointer equal to the node's only child.

3. The node has two children:

This is the most complicated case.

If we just remove the node, then the tree will be split into two pieces so it will no longer be a tree. We will need to find a new root of the subtree that we are deleting. We also must obey the rules governing binary search trees, so we can't use any node for the new node.

There are only two nodes that we can use for the new root, either the smallest value on the right, or the largest value on the left.

We can then swap the data at those two nodes, as shown in the center picture above. Then there will be a duplicate node, so we must then delete that one (which we can do recursively).

## Algorithm

The algorithm to remove a node from a binary search tree is as follows:

1. If the node has no children, return null to its parent.
2. If the node has only a left child, return node.left to its parent, bypassing it.
3. If the node has only a right child, return node.right to its parent, bypassing it.
4. If the node has two children:
1. Find the node with the least value in the node.right subtree.
2. Swap the data at the least node with the one we want to remove.
3. Remove the least node.

To find the smallest node on a subtree we can use the following algorithm:

1. If the node at the root of the subtree has no left child, return the data at the root.
2. Otherwise recursively find the smallest node on the left subtree.

BinarySearchTree.java contains all of the necessary code dealing with binary search trees so far, including inserting, searching, and now removing.