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

FIGURE 25-4

(a) A binary search tree; (b) the same tree after adding Chad

(a) (b)

Jared Jared

Brittany Megan

Brittany Megan

Brett Doug Jim Whitney Brett Doug Jim Whitney

Chad

Question 6 Add the names Chris , Jason , and Kelley to the binary search tree in Figure 25-4b.

Question 7 Add the name Miguel to the binary search tree in Figure 25-4a, and then add
Nancy . Now go back to the original tree and add Nancy and then add Miguel . Does the order
in which you add the two names affect the tree that results?

A Recursive Implementation
25.13

The method add has an elegant recursive implementation. Consider again the example given in
the previous segment. If we want to add Chad to the binary search tree in Figure 25-4a, we
take the following steps:

•

To add Chad to the binary search tree whose root is Jared :
Observe that Chad is less than Jared .
Add Chad to Jared 's left subtree, whose root is Brittany .

•

To add Chad to the binary search tree whose root is Brittany :
Observe that Chad is greater than Brittany .
Add Chad to Brittany 's right subtree, whose root is Doug .

•

To add Chad to the binary search tree whose root is Doug :
Observe that Chad is less than Doug .
Since Doug has no left subtree, make Chad the left child of Doug .

We can see that adding an entry to the tree rooted at Jared depends upon adding to progressively
smaller subtrees, as Figure 25-5 shows.