Deleting BST Nodes

We have the following tree:

Now suppose that we're asked to delete a node associated with a particular value in the tree. Call it the target node. How might we do so? Once again, because we know how to search for nodes, deleting is almost trivial, at least for tree's leaves. We just to search for the particular node containing the key, then delete if found. For the leaves, this is straightforward. If we wanted to delete the node containing 70, we just have call search(root, 70), then, when we get to 70, delete:

All that's left to do after deleting node(70) is to ensure its parent, node(60) has its left-child pointer set to NULL. Now, we emphasized almost trivial because there's a bit of a troublesome case: Deleting branch nodes. For example, suppose we were asked to delete the node containing 60. If we just blindly deleted the node, we'd end up with:

We've partitioned the tree, and that's likely not what we intended. But even if we did, assuming the only way to access the tree was through a single root pointer, the other tree — node(55) — is lost in memory; from a practical perspective, we've essentially destroyed it.

To avoid this problem: Before deletion, always check if the target node is a branch node or a leaf node. If the target node is a branch node with only one child, as is the case with node(60), then the target node must take its parent's place after deletion:

This avoids partitioning, but only for deleting uniparous nodes. What if we were now asked to delete node(50)? Once again, blindly deleting causes a partition:

There are several ways to avoid this problem. One way is to fill the newly-emptied position with the target node's inorder predecesor. In other words, fill the vacancy with the node that comes before the target node within the tree's inorder traversal sequence. For our tree above, the inorder traversal sequence is:

and we can see that node(40) comes before node(50). Above, we've also indicated the blue-colored node(55), node(50)'s inorder successor. Thus, if we delete a biparous node, we can choose either the inorder predecesor or the inorder successor to fill the vacancy:

Inorder predecessor sucession:

Inorder successor succession:

Given the binary search tree's structure, finding either of these successors is easy enough, per the following lemmas:

Definition: Inorder Predecesor. Let ${N}$ be a node in a binary search tree ${B.}$ The inorder predecesor of ${N}$ is the rightmost child of ${B}$'s left subtree.

Definition: Inorder Successor. Let ${N}$ be a node in a binary search tree ${B.}$ The inorder successor of ${N}$ is the leftmost child of ${B}$'s right subtree.

We call this vacancy-filling technique inorder-succession. Having given a broad overview of how the technique works, let's point out some of the flaws with this technique. First, suppose we had the following tree:

The inorder traversal squence for this tree is:

If we deleted node(20) using inorder-successor-succession, then we suddenly have to perform several successions:

Before deletion. No changes.

Remove node(20). There's a vacancy that must be filled, and because we're using inorder-successor-succession, node(30) must rise to fill the vacancy. In this case, it becomes the left-child of node(90).

The previous step results in a vacancy, and now node(70) must succeed.

Now node(80) must succeed.

And finally, node(90) must succeed, which means node(30) must succeed.