Remarks on the Binary Tree Programming Assignment

Explicit constructor calls in constructors

The : notation in the BinarySearchTree copy constructor

  BinarySearchTree( const BinarySearchTree *src ) : BinaryTree<T>(src) {}

calls the corresponding superclass (BinaryTree) copy constructor directly. The constructor still has a body, but in this particular case it is empty.

The same notation is used to call a constructor for fields of the class. For example, the BTNode constructors could (and arguably should) be written as

  BTNode( T element, BTNode* left_ptr = NULL, BTNode* right_ptr = NULL ) :
    elem(element), left(left_ptr), right(right_ptr) {}

  BTNode( const BTNode& src ) :
    elem(src.elem), left(src.left), right(src.right) {}

Values vs. Pointers as Node Elements

By design, the elem field of a tree node contains an actual value rather than a pointer to a value. That means the elements are actually copied as they are added to the tree. It can be argued that this is wasteful, and it would be better to store only a pointer to the node element in each node instead. Also, the copying requirement restricts the possible type of the elements to those that have copy constructors and perhaps even = operators, depending on how the code is written. Using pointers also allows for the element of a node to be NULL, which can be useful in some tree algorithms. Storing pointers only eliminates the issue of having to destroy the element values when the tree is destroyed. And of course there is the issue of the extra memory required by the copy. Nonetheless, storing the values directly has its own set of advantages that ultimately wins out. Here is why.

For simple types, it beneficial to store the values directly. For example, if we have
```
BinarySearchTree tree;
```
It is nice to be able to write tree.insert(17), rather than assign a variable containing 17, pass the address, and make sure that we don't lose that variable. For simple types, copying that isn't a problem, as it's no more effort to copy an int or double than to copy a pointer. And the space required may well be less than the space required for a pointer.
The one class type most likely to be used for the tree nodes is string, which has all the necessary functionality for copying.
Storing pointers means that the element value has to be kept somewhere in memory, and we have to keep track of that allocation. Depending on the application, that may or may not be a problem. But it certainly is a problem if we want to use the tree itself to store the elements, certainly a reasonable use of the class.
Using pointers to node elements has more potential to violate tree properties. For example, a valid binary search tree can become invalid if the key of any of the node elements is changed. Key constancy can't be enforced if the element values are outside the tree.
The C++ automatic destructor calling sequence transparently handles the destruction of the node elements, so tree destruction really isn't that much of a problem.
Finally, and perhaps most importantly, the node elements can be pointers, effectively, although it's not as simple as BinarySearchTree<string*> tree. (That works, but the comparision operations compare the pointers not the node elements). To store element pointer, we can define a simple wrapper structure something like
```
struct StringPointer {
  string *ptr;
  StringPointer( const StringPointer& src ) { ptr = src.ptr; }
  bool operator==( const StringPointer& src ) { return ptr->equals(*(src.ptr)); }
  ⋮
```
and then use BinarySearchTree<StringPointer> tree;

Templates

Templates in C++ are comparatively kludgey. All that really happens with a template class or function is that the class parameters are replaced, verbatim, with the actual class or type name supplied when the template is invoked. For example

template class MyClass {
 public:
  T value;
  bool equals( const MyClass& src ) const {
    return (value == src.value);
  }
};

gets translated to

class MyClass_int {
 public:
  int value;
  bool equals( const MyClass_int& src ) const {
    return (value == src.value);
  }
};

when invoked as MyClass<int>. For a more general class, MyClass<SomeClass>

class MyClass_SomeClass {
 public:
  int value;
  bool equals( const MyClass_SomeClass& src ) const {
    return (value == src.value);
  }
};

If SomeClass doesn't have an == operator defined, it won't compile: the compiler will report an error something like

 no match for `operator==' in `((const MyClass*)this)->MyClass::value == src.MyClass::value'

There is no direct way in C++ to force the type of a template class parameter to have certain functionality when the template object is defined. You have to rely on compilation failure to enforce template types. We're doing that with the type T of the elem field of a BTNode in several places. In the insertion and look-up methods, we have to assume that T has ==, <, and > operators that work properly.

The binary tree search prototype

template T* lookup( const K& key ) const;

introduces a second class parameter K which refers to the type of the search key. For the lookup method, we could assume the element type T has a get_key() method and then compare the key argument to the result of the get_key() method on each node element. The problem, though, is that simple C++ types have no such method, and to make the tree classes useful we really should let them work with simple types. Instead we just to assume that there are == and < (and perhaps >) operators available that can directly compare the key type K with the node element type T. That is certainly true if the tree node elements are simple types, and therefore their own key. If we wanted to use something more complicated for the node elements, such as a structure with a key and other data, we have to include appropriate == and < operators for that class.