A Binary Search Tree Implementation - Data Structures and Abstractions with Java - page 644

FIGURE 25-11

(a) A binary search tree; (b) after removing Chad ; (c) after removing Sean ;
(d) after removing Kathy

(a) (b)

Megan Megan

Sean

Kathy Sean Kathy

Brett Lance Pat Whitney Brett Lance Pat Whitney

Reba

Chad Maria Reba Zak Brittany Maria Zak

Brittany Doug Doug

Derek Derek

Dirk Dan Dirk

Dan

(c) (d)

Megan Megan

Kathy Reba Doug Reba

Brett Pat Whitney Pat Whitney

Lance Brett Lance

Brittany Maria Zak Brittany Maria Zak

Doug Derek

Derek

Dan Dirk

Dan Dirk

Question 8 The second algorithm described in Segment 25.25 involves the inorder
successor. Using this algorithm, remove Sean and Chad from the tree in Figure 25-11a.

Question 9 Remove Megan from the tree in Figure 25-11a in two different ways.

Removing an Entry in the Root
25.27

Removing an entry that is in the root of the tree is a special case only if we actually remove the root
node. That will occur when the root has at most one child. If the root has two children, the previous
segment shows that we would replace the root's entry and delete a different node.
If the root is a leaf, the tree has only one node. Deleting it results in an empty tree. If the root
has one child, as Figure 25-12 illustrates, the child is either a right child or a left child. In either
case, we simply delete the root node by making the child node C the root of the tree.