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

parent parent

current

may be a left or
right child of

current
node is replaced by the content of
the

The content of the

parent

current current

points to the node
to be deleted

current

rightMost rightMost node. The

node is deleted.

Right subtree Right subtree

.
.
.

.
.
.

parentOfRightMost parentOfRightMost

rightMost Content copied to

current

and the node

null

is deleted

leftChildOfRightMost leftChildOfRightMost

(a) (b)

F IGURE 25.12

Case 2: The current node has a left child.

root 20 root 16

10 40 10 40

rightMost

16 30 80 30 80

14 27 50 14 27 50

(a) (b)

F IGURE 25.13

Case 2: Deleting node 20 from (a) results in (b).

The algorithm for deleting an element from a binary search tree can be described in
Listing 25.7.

delete method

L ISTING 25.7 Deleting an Element from a BST

1 boolean delete(E e) {
2 Locate element e in the tree;
3

not in the tree

if element e is not found