## Sample Programming Assignments

### Data Structures and Other Objects Using C++ Second Edition by Michael Main and Walter Savitch ISBN 0-201-70297-5, Softcover, 816 pages

Section 10.3 of the Second Edition includes a class for binary tree nodes. Among other things, there are two member functions to get copies of the left and right pointers of a node. From page 465, we have these functions:
```   ...
binary_tree_node* left( ) { return left_field; }
binary_tree_node* right( ) { return right_field; }
```
We recommend a slight change to these functions, so that the return type is a reference to the left and right pointers, indicated by the ampersand in the return type shown here:
```   ...
binary_tree_node*& left( ) { return left_field; }
binary_tree_node*& right( ) { return right_field; }
```
This modified version of the binary tree node is available to download from www.cs.colorado.edu/~main/chapter10/bintree.h and it will also appear in the second printing of the textbook.

Using a reference in the return type has some simple advantages that we can illustrate by considering a call to `p->left()` (for some pointer `p`). When the return value is a reference, then we can use `p->left()` to directly reference the left link in a node. For example, we can write:

```    p->left() = NULL;
```
This is a small advantage only, but a larger advantage also occurs because we can also use p->left() in any location that expects a variable that is a pointer to a binary tree node. In particular, recursive functions are often written to manipulate a binary tree, and one of the parameters to such a function is sometimes a reference parameter that points to one of the nodes. For example, from Section 10.5:
```    template <class Item>
bool bst_remove(binary_tree_node<Item>*& root_ptr, const Item& target)
// Precondition: root_ptr is a root pointer of a binary search tree
// or may be NULL for an empty tree).
// Postcondition: If target was in the tree, then one copy of target
// has been removed, and root_ptr now points to the root of the new
// (smaller) binary search tree. In this case the function returns true.
// If target was not in the tree, then the tree is unchanged (and the
// function returns false).
{
binary_tree_node<Item> *oldroot_ptr;

if (root_ptr == NULL)
{   // Empty tree
return false;
}

if (target < root_ptr->data( ))
{   // Continue looking in the left subtree
// Note: Any change made to root_ptr->left by this recursive
// call will change the actual left pointer (because the return
// value from the left() member function is a reference to the
// actual left pointer.
return bst_remove(root_ptr->left( ), target);
}

if (target > root_ptr->data( ))
{   // Continue looking in the right subtree
// Note: Any change made to root_ptr->right by this recursive
// call will change the actual right pointer (because the return
// value from the right() member function is a reference to the
// actual right pointer.
return bst_remove(root_ptr->right( ), target);
}

if (root_ptr->left( ) == NULL)
{   // Target was found and there is no left subtree, so we can
// remove this node, making the right child be the new root.
oldroot_ptr = root_ptr;
root_ptr = root_ptr->right( );
delete oldroot_ptr;
return true;
}

// If code reaches this point, then we must remove the target from
// the current node. We'll actually replace this target with the
// maximum item in our left subtree.
// Note: Any change made to root_ptr->left by bst_remove_max
// will change the actual left pointer (because the return
// value from the left() member function is a reference to the
// actual left pointer.
bst_remove_max(root_ptr->left( ), root_ptr->data( ));
return true;
}
```
In this function, any changes to the root_ptr (such as moving it down to its right child) will affect the actual argument (since it is a reference parameter). Feel free to send me email if you'd like to discuss this more.