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

FIGURE 25-5

Recursively adding Chad to smaller subtrees of a binary search tree

(a) Chad

Jared

Megan

Brittany

Brett Doug Jim Whitney

(b)

Jared

Chad

Brittany Megan

Brett Jim Whitney

Doug

(c)

Jared

Brittany Megan

Chad

Brett Doug Jim Whitney

(d)

Jared

Brittany Megan

Brett Doug Jim Whitney

Chad

25.14

A recursive algorithm for adding a new entry. The following recursive algorithm formalizes this
approach, in accordance with the specifications of the method add in SearchTreeInterface .
Recall that we decided to have only distinct entries in the binary search tree. If we try to add an
entry to a tree that matches an entry already in the tree, we replace that entry with the new entry and
return the old entry.