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.
The node is a leaf:
In this case, we can simply remove the node, and set the link to it to null.
The node has one child:
In this case, we must set the parents pointer equal to the node's only child.
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).
The algorithm to remove a node from a binary search tree is as follows:
To find the smallest node on a subtree we can use the following algorithm:
BinarySearchTree.java contains all of the necessary code dealing with binary search trees so far, including inserting, searching, and now removing.
Copyright © 2021 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.