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

To simplify our algorithm, let's assume for the moment that the binary search tree is not empty:
Algorithm addEntry(binarySearchTree, newEntry)
// Adds a new entry to a binary search tree that is not empty.
// Returns null if newEntry did not exist already in the tree. Otherwise, returns the
// tree entry that matched and was replaced by newEntry .

result = null
if (newEntry matches the entry in the root of binarySearchTree)
{

result = entry in the root
Replace entry in the root with newEntry

}
else if (newEntry < entry in the root of binarySearchTree)
{

if ( the root of binarySearchTree has a left child )
result = addEntry( left subtree of binarySearchTree, newEntry)
else
Give the root a left child containing newEntry

}
else // newEntry > entry in the root of binarySearchTree
{

if ( the root of binarySearchTree has a right child )
result = addEntry( right subtree of binarySearchTree, newEntry)
else
Give the root a right child containing newEntry

}

return result

We can handle the addition to an empty binary search tree as a special case within another
algorithm that invokes addEntry , as follows:
Algorithm add(binarySearchTree, newEntry)
// Adds a new entry to a binary search tree.
// Returns null if newEntry did not exist already in the tree. Otherwise, returns the
// tree entry that matched and was replaced by newEntry .

result = null
if (binarySearchTree is empty )
Create a node containing newEntry and make it the root of binarySearchTree
else
result = addEntry(binarySearchTree, newEntry)

return result;

25.15

The private recursive method addEntry . Recall the recursive search algorithm given in Segment 25.7.
The public method getEntry in Segment 25.9 invokes a private recursive method findEntry that imple-
ments the search algorithm. We have a similar organization here. The public method add calls a private
recursive method addEntry , if the tree is not empty. Like findEntry , addEntry has a node as a parameter
that is initially the root node of the tree. When addEntry is called recursively, this parameter is either the
left child or the right child of the current root.
Remember where we place a new node into a binary search tree. As Figures 25-4 and 25-5 illus-
trate, a new node always becomes a leaf in the tree. Now imagine the recursive calls to addEntry
when adding Chad to the tree in Figure 25-5a. Eventually, the node containing Doug is passed to
addEntry as its argument (Figure 25-5c). Since Chad is less than Doug , and Doug 's node has no left
child, addEntry creates one containing Chad (Figure 25-5d).