Introduction to Binary Trees - Advanced Topics in Java: Core Concepts in Data Structures - page 247

Case 1 is easy. For example, to delete P , we simply set the right subtree of N to null. Case 2 is also easy. To delete
A (no left subtree), we replace it by C , its right subtree. And to delete F (no right subtree), we replace it by A , its left
subtree.
Case 3 is a bit more difficult since we have to worry about what to do with the two subtrees hanging off the node.
For example, how do we delete L ? One approach is to replace L by its in-order successor, N , which must have an
empty left subtree. Why? Because, by definition, the in-order successor of a node is the first node (in order) in its right
subtree. And this first node (in any tree) is found by going as far left as possible.
Since N has no left subtree, we will set its left link to the left subtree of L . We will set the left link of the parent of N
( R in this case) to point to P , the right subtree of N . Finally, we will set the right link of N to point to the right subtree of L ,
giving the tree shown in Figure 8-10 .

H

N

F

R

A J

T

P

C

D

B

Figure 8-10. BST after deletion of L in Figure 8-9

Another way to look at it is to imagine the contents of node N being copied into node L . And the left link of the
parent of N (which is R) is set to point to the right subtree of N (which is P ).
In our algorithm, we will treat the node to be deleted as the root of a subtree. We will delete the root and return a
pointer to the root of the reconstructed tree.

deleteNode(TreeNode T) {
if (T == null) return null
if (right(T) == null) return left(T) //cases 1 and 2b
R = right(T)
if (left(T) == null) return R //case 2a
if (left(R) == null) {
left(R) == left(T)
return R
}

T

T

R

T

R

while (left(R) != null) { //will be executed at least once
P = R
R = left(R)
}