BINARY SEARCH TREES - Introduction to Java Programming: Comprehensive Version - page 944

parent parent

current may be a left or
right child of parent

Subtree may be a left or
right subtree of parent

current

current points the node
to be deleted

No left child

Subtree

Subtree

(a)

(b)

F IGURE 25.10

Case 1: The current node has no left child.

root 20 root 20

10 40 40

16 30 80 16 30 80

27 50 27 50

(a) (b)

F IGURE 25.11

Case 1: Deleting node 10 from (a) results in (b).

Note
If the current node is a leaf, it falls into Case 1. For example, to delete element 16 in
Figure 25.11a, connect its right child (in this case, it is null ) to the parent of node 16 .

delete a leaf

Case 2: The current node has a left child. Let rightMost point to the node that contains the
largest element in the left subtree of the current node and parentOfRightMost point to the
parent node of the rightMost node, as shown in Figure 25.12a. Note that the rightMost node
cannot have a right child but may have a left child. Replace the element value in the current
node with the one in the rightMost node, connect the parentOfRightMost node with the
left child of the rightMost node, and delete the rightMost node, as shown in Figure 25.12b.
For example, consider deleting node 20 in Figure 25.13a. The rightMost node has the
element value 16 . Replace the element value 20 with 16 in the current node and make node
10 the parent for node 14 , as shown in Figure 25.13b.

Note
If the left child of current does not have a right child, current.left points to the
large element in the left subtree of current . In this case, rightMost is current.
left and parentOfRightMost is current . You have to take care of this special
case to reconnect the right child of rightMost with parentOfRightMost .

special case