Find the size of an integer data type without using sizeof() function.

Listing D is an example of one solution. What is not mentioned in the question is if the integer data type is signed or unsigned. Does your solution work for both? For edge-case support, we can assume that the integer data type has at least one bit because a 0-bit integer data type is pretty useless. Does your solution work for 1 or 2 bit integers, or did you assume that integers were a multiple of 8 bits?

#include <stdio.h>

template< typename IntType >
int numberOfBits() {
  IntType newValue = 1;
  IntType oldValue = 0;
  int numBits = 0;
  while(oldValue != newValue) {
    ++numBits;
    oldValue = newValue;
    newValue = (newValue << 1) + 1;
  }
  return numBits;
}

int main(int argc, char* argv[]) {
  printf("sizeof(int)  : %d\n", sizeof(int) * 8);
  printf("size of <int>: %d\n", numberOfBits<int>());
  printf("\n");
  printf("sizeof(unsigned int)  : %d\n", sizeof(unsigned int) * 8);
  printf("size of <unsigned int>: %d\n", numberOfBits<unsigned int>());
  printf("\n");
  printf("sizeof(short)  : %d\n", sizeof(short) * 8);
  printf("size of <short>: %d\n", numberOfBits<short>());
  return 0;
}

#include <iostream>

template <typename T>
void SizeOf()
{
  T a[2];
  std::cout << "sizeof() = " << 8 * sizeof(T) << std::endl;
  std::cout << "SizeOf<> = ";
  std::cout << 8 * (((long int)((T*)a+1)) - ((long int)(T*)a));
  std::cout << std::endl;
}

int main( )
{
  SizeOf<unsigned int>();
}

Multiply an integer by 8 without using multiplication or addition.

The key to the answer to this question is knowing about the shift operator and how it relates to the integer’s internal representation. The following code snippet answers this question:

int x = 3;
x = x << 3;

Array destruction

An array that is instantiated with the new[] operator should also be deleted using the delete[] operator. Write a program that proves that the destructors for an array are not called when the array was instantiated with new [] and the array was deleted with delete (without the delete[] syntax).

My first version of the array destruction test in Listing F did not use the VCL (a Borland C++ compiler feature) and an access violation was thrown at runtime. I tried to wrap the delete with a try/catch, but the exception still wasn’t caught. The debugger told me that an EAccessViolation exception was being thrown and the C++ Builder Help told me that it was defined in the VCL. So I converted the program to use the VCL and tried it again. The VCL version does not cause an access violation at runtime, so I removed the try/catch block in the code.

// An array that is instantiated with the new[] operator 
// should also be deleted using the delete[] operator.  
// Write a program that proves that the destructors for 
// an array are not called when the array was instantiated 
// with new [] and the array was deleted with delete 
// (without the delete[] syntax).

// This program took 15 minutes to write and debug.

#include <vcl.h>
#include <iostream>

using namespace std;   // okay for small programs

int g_LiveInstances = 0;

struct Trivial {
  Trivial() {
    cout << "Creating object #" << ++g_LiveInstances << endl;
  }
  virtual ~Trivial() {
    cout << "Deleting an object" << endl;
    --g_LiveInstances;
  }
};

int main(int, char**) {
  Trivial *p = new Trivial[5];
  delete p;

  // This should show:
  //    Number of Trivial instantiations remaining: 4
  cout << "Number of Trivial instantiations remaining: ";
  cout << g_LiveInstances << endl;
  return 0;
}

Caseless string comparison

Write a String class that compares its strings by ignoring the case of the characters.

I had two choices when writing the caseless string comparison solution in Listing G. I could either create my own string class that stores a string using a has-a relationship or I could override the compare method in the std::char_traits class. The former would require me to write helper functions for all of the public and protected constructors and methods. I chose the latter solution because its code should be limited to a specialized std::char_traits class.

Notice that I didn’t have to write any specialized comparison methods (operator==, operator<, operator>, and others). I used the template supplied by the STL, which calls _Traits::compare(). The static compare() method in CaselessTrait was created by debug-tracing a normal std::string comparison into the char_traits.h file. I copy-pasted the definition of compare() from char_traits into the solution and changed the comparison function from memcpy to strnicmp.

// Code and debug time:  35 minutes.

#include <iostream>
#include <string>

template <class _CharT>
class CaselessTrait : public std::char_traits<_CharT>
{
public:
  static int _STLP_CALL compare(const char* __s1, 
                                const char* __s2, 
                                size_t __n)
    { return strnicmp(__s1, __s2, __n); }

};

// Not asked for by the problem but I threw it in anyway
std::ostream
&operator<<(std::ostream &os,
            const std::basic_string<char, CaselessTrait<char>, 
            std::allocator<char> > &obj
           )
{
  os << obj.c_str();
  return os;
}

int main(int, char**) {
  typedef std::basic_string<char, CaselessTrait<char> > CaselessString;
  CaselessString test1 = "Hello World";
  CaselessString test2 = "hello world";

  std::cout << test1 << std::endl;
  std::cout << test2 << std::endl;

  if (test1 == test2) {
    std::cout << "Strings are equal" << std::endl;
  }
  else {
    std::cout << "String are not equal" << std::endl;
  }
  return 0;
}

Time difference

A comma-delimited file has two columns: timeA and timeB. Both columns are times in the following format: hh:mm [a|p]m

where:
hh is from 1 to 12.
mm is from 1 to 60.
[a|p] is either an ‘a’ or ‘p’.

Example file:
5:57 pm,10:37 am
Write a program that reads the comma-delimited text file. For each line in the text file, report the time that is earlier. Assume all times are in the same time zone and that all times are for the same day.

The time comparison solution in Listing H primarily converts both times into the number of minutes past midnight and then simply compares those two values. I added some code that reports errors, such as when the file can’t be opened or when the data format is grossly wrong.

The parsing algorithm in decodeTime() assumes the data is in the right format. The problem doesn’t require anything more than this but in a real interview I would ask if the program should check for incorrectly formatted data or invalid data, such as 11:88am. My am/pm detection only checks for “pm” and assumes all other values, including “PM”, are “am”. I could have easily used stricmp instead of operator==(), but at that point in the parser I was assuming that the data would be correctly formatted. These are the kinds of tradeoffs one makes when keeping the solution simple and staying within the deadline.

// Code and debug time:  45 minutes

#include <fstream>
#include <iostream>

// okay for small programs
using namespace std;

// Time converted to the number of minutes past midnight
typedef unsigned int Time;

// Given a data value of the form:
//   hh:mm [a|p]m
// convert the string to the number of
// minutes past midnight.
Time decodeTime(const string text) {
  string::size_type colonPos = text.find(':');
  string::size_type blankPos = text.find(' ');

  int hours = atoi(text.substr(0, colonPos).c_str());
  int mins  = atoi(text.substr(colonPos+1, blankPos-colonPos).c_str());
  string amPm = text.substr(blankPos+1);

  // "midnight" and "noon" are special because we want
  // the number of minutes past midnight... so switch a 12 into
  // a 0 to accomodate the calculation.
  if (hours == 12) hours = 0;

  Time minsPastMidnight = mins;

  if (amPm == "pm")
    minsPastMidnight += (12 + hours) * 60;
  else
    minsPastMidnight += hours * 60;

  return minsPastMidnight;
}

int main(int argc, char* argv[]) {
  ifstream csv("data.csv", ios::in);
  if (!csv) {
    cout << "Can not open data.csv\n";
    return 1;
  }

  string line;   // line from CSV file
  while (getline(csv, line, '\n')) {
    // find the ',' separator
    string::size_type commaPos = line.find(',');
    if (commaPos == string::npos) {
      cout << "Invalid CSV line: " << line << endl;
    }
    else {
      Time firstTime = decodeTime(line.substr(0, commaPos));
      Time secondTime = decodeTime(line.substr(commaPos+1));
      if (firstTime < secondTime)
        cout << line.substr(0, commaPos) << endl;
      else
        cout << line.substr(commaPos+1) << endl;
    }
  }
  return 0;
}

Recursive sort

Sort a linked list using recursion.

The recursive sort algorithm in Listing I took a lot longer than I would have expected. My implementation assumes that only the head pointer is available. A flag, sortAgain, is initialized to false and is used to tell Sort() if any of the nodes in the list were swapped. If RecursiveSort() returns with sortAgain still false, the list has been sorted. Otherwise, sortAgain is reset to false and the list is resorted.

To keep the algorithm simple, I didn’t make any attempt to keep track of the sorted and unsorted parts of the list. The entire list is sorted every time RecursiveSort is called.

Recursive sort solutions that swap the key values or swap the struct’s payload values should be considered failures. Shuffling the data inside of the list defeats the purpose of using a linked list. The main reason for using a linked list is because the data is supposedly large or difficult to copy. If that were not the case, then an array would have been used. List nodes are being used to point to the data. The head pointer and the next pointers are the only parts of the list that need to be modified to sort it.

Don’t forget to test your final solution for an empty list and for a list with only one item in it. The first version of my algorithm would have thrown an access violation for an empty list.

// Code and debug time: 1 hour, ten minutes.

#include <stdlib.h>   // for rand()
#include <algorithm>
#include <function>
#include <iostream>

struct List {
  List(int val) : key(val), next(NULL)
  {}
  int key;
  List *next;
};

// Called by Sort(List *) to recursively sort the
// linked list.
//
List * RecursiveSort(List *current, List *prev, bool &sortAgain) {
  List *head = current;

  if (current == NULL || current->next == NULL)
    return current;    // nothing to sort

  if (current->key > current->next->key) {
    if (prev == NULL) {
      head = current->next;
      current->next = head->next;
      head->next = current;
      current = head;
      sortAgain = true;
    }
    else {
      // The unsorted order of the nodes is:
      //    prev, current, node, after
      // The sorted order of the nodes is:
      //    prev, node, current, after
      List *node = current->next;
      List *after = node->next;

      head = current->next;
      prev->next = node;
      current->next = after;
      node->next = current;

      sortAgain = true;
    }
  }

  if (current->next != NULL) {
    RecursiveSort(current->next, current, sortAgain);
  }

  return head;
}

// Sort the single-linked list.
List * Sort(List *head) {
  // Keep sorting the list until the entire
  // list is sorted.
  bool sortAgain = false;
  do {
    sortAgain = false;
    head = RecursiveSort(head, NULL, sortAgain);
  } while (sortAgain == true);
  return head;
}

// Print the keys of the list separated by commas.
void Print(const List *head) {
  const List *node = head;
  std::cout << "List: ";
  while (node != NULL) {
    std::cout << node->key << ",";
    node = node->next;
  }
  std::cout << "\n";
}

int main(int, char**)
{
  // Create an unsorted array that will
  // be transformed into an unsorted linked
  // list.
  int a[10];
  const int numElements = sizeof(a) / sizeof(int);
  for(int i = 0; i < numElements; ++i)
    a[i] = i * (i % 2 ? -1 : 1);
  randomize();
  std::random_shuffle(&a[0], &a[numElements]);

  // Transfer the unsorted array into a list...
  List *head = NULL;
  List *tail = NULL;
  for(int i = 0; i < numElements; ++i) {
    List *node = new List(a[i]);
    if (head == NULL) {
      head = node;
      tail = node;
    }
    else {
      tail->next = node;
      tail = node;
    }
  }

  std::cout << "Before sort:\n";
  Print(head);

  head = Sort(head);

  std::cout << "\nAfter sort:\n";
  Print(head);

  return 0;
}

Iterative list sorting

Sort a linked list without using recursion.

Listing J shows my solution for nonrecursively sorting the single-linked list. I cheated a little bit and used the recursive sort solution from listing I as a starting point. It’s not really cheating, though, because I’m allowed to use whatever resources are available.

In the process of looking at the swap algorithm a second time, I noticed it could be improved a little. I think the version in listing J is a little clearer because only the work that’s needed for the boundary condition (the very first element in the list) is inside of the if statement.

// Code and debug time: 15 minutes (using the RecursiveSort.cpp 
// as a starting point)

#include <stdlib.h>   // for rand()
#include <algorithm>
#include <function>
#include <iostream>

struct List {
  List(int val) : key(val), next(NULL)
  {}
  int key;
  List *next;
};

// Sort the single-linked list.
List * Sort(List *head) {
  if (head == NULL || head->next == NULL)
    return head;    // nothing to sort

  List *prev = NULL;
  List *current = NULL;

  bool sortAgain = false;
  do {
    sortAgain = false;
    current = head;
    prev = NULL;
    while (current != NULL && current->next != NULL) {
      if (current->key > current->next->key) {
        sortAgain = true;

        // The unsorted order of the nodes is:
        //    prev, current, node, after
        // The sorted order of the nodes is:
        //    prev, node, current, after
        List *node = current->next;
        List *after = node->next;

        if (prev == NULL) {
          head = current->next;
        }
        else {
          prev->next = node;
        }
        current->next = after;
        node->next = current;
      }
      prev = current;
      current = current->next;
    }
  } while (sortAgain == true);

  return head;
}

// Print the keys of the list separated by commas.
void Print(const List *head) {
  const List *node = head;
  std::cout << "List: ";
  while (node != NULL) {
    std::cout << node->key << ",";
    node = node->next;
  }
  std::cout << "\n";
}

int main(int, char**)
{
  // Create an unsorted array that will
  // be transformed into an unsorted linked
  // list.
  int a[10];
  const int numElements = sizeof(a) / sizeof(int);
  for(int i = 0; i < numElements; ++i)
    a[i] = i * (i % 2 ? -1 : 1);
  randomize();
  std::random_shuffle(&a[0], &a[numElements]);

  // Transfer the unsorted array into a list...
  List *head = NULL;
  List *tail = NULL;
  for(int i = 0; i < numElements; ++i) {
    List *node = new List(a[i]);
    if (head == NULL) {
      head = node;
      tail = node;
    }
    else {
      tail->next = node;
      tail = node;
    }
  }

  std::cout << "Before sort:\n";
  Print(head);

  head = Sort(head);

  std::cout << "\nAfter sort:\n";
  Print(head);

  return 0;
}

Reversing a single linked list

Reverse a single-linked list without using recursion.

My solution for reversing the single-linked list, in Listing K, was based on the code in Listing J. The solution does not overwrite the next pointer for the head node until the entire list has been sorted. I thought this would be easier than checking, on each loop iteration, if the head node was being modified.

As with the sorting solutions, any solutions that involve moving the data values instead of changing the head and next pointers is a failure.

If I were to provide the linked list problems as an interviewer, I would provide everything in the solution except for the sorting or reversing method and everything in the main() function up to the first Print method.

// Code and debug time: 20 minutes (using the 
// IterativeSort.cpp as a starting point)

#include <iostream>

struct List {
  List(int val) : key(val), next(NULL)
  {}
  int key;
  List *next;
};

// Print the keys of the list separated by commas.
void Print(const List *head) {
  const List *node = head;
  std::cout << "List: ";
  while (node != NULL) {
    std::cout << node->key << ",";
    node = node->next;
  }
  std::cout << "\n";
}

List * ReverseList(List *head) {
  if (head == NULL || head->next == NULL)
    return head;    // Nothing to reverse;

  // Reverse the list except for the
  // head node.
  List *prev = head;
  List *current = prev->next;
  while (current != NULL) {
      List *after = current->next;
      current->next = prev;    // reverse the list
      prev = current;
      current = after;
  }

  // In the reversed list, the head element becomes
  // the last element, so terminate the list at
  // the head element
  head->next = NULL;
  return prev;
}

int main(int, char**)
{
  const int numElements = 10;

  // Create a list from 0..9:
  List *head = NULL;
  List *tail = NULL;
  for(int i = 0; i < numElements; ++i) {
    List *node = new List(i);
    if (head == NULL) {
      head = node;
    }
    else {
      tail->next = node;
    }
    tail = node;
  }

  std::cout << "Before Reverse:\n";
  Print(head);

  head = ReverseList(head);

  std::cout << "\nAfter Reverse:\n";
  Print(head);

  return 0;
}

How do I convert an integer to a string?
A: The simplest way is to use a stringstream:

#include
#include
#include
using namespace std;
string itos(int i) // convert int to string
{
  stringstream s;
  s << i;
  return s.str();
}
int main()
{
  int i = 127;
  string ss = itos(i);
  const char* p = ss.c_str();
  cout << ss << ” ” << p << “\n”;
}

Naturally, this technique works for converting any type that you can output using << to a string.

Q: Implement a Algorithm to check if the link list is in Ascending order?
A: template

bool linklist::isAscending() const{
    nodeptr ptr = head;
    while(ptr->_next)  {
        if(ptr->_data > ptr->_next->_data)
            return false;
        ptr= ptr->_next;
    }
    return true;
}

Q: Write an algorithm to reverse a link list?
A: template

void linklist::reverselist()   {
  nodeptr ptr= head;
  nodeptr nextptr= ptr->_next;
  while(nextptr)  {
    nodeptr temp = nextptr->_next;
    nextptr->_next = ptr;
    ptr = nextptr;
    nextptr = temp;
  }
  head->_next = 0;
  head = ptr;
}

Q: Implement Binary Heap in C++?
A:
BinaryHeap.h

#ifndef BINARY_HEAP_H_
#define BINARY_HEAP_H_
#include “dsexceptions.h”
#include “vector.h”
// BinaryHeap class
//
// CONSTRUCTION: with an optional capacity (that defaults to 100)
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) –> Insert x
// deleteMin( minItem ) –> Remove (and optionally return) smallest item
// Comparable findMin( ) –> Return smallest item
// bool isEmpty( ) –> Return true if empty; else false
// bool isFull( ) –> Return true if full; else false
// void makeEmpty( ) –> Remove all items
// ******************ERRORS********************************
// Throws Underflow and Overflow as warranted
template class BinaryHeap  {
public:
  explicit BinaryHeap( int capacity = 100 );
  bool isEmpty( ) const;
  bool isFull( ) const;
  const Comparable & findMin( ) const;
  void insert( const Comparable & x );
  void deleteMin( );
  void deleteMin( Comparable & minItem );
  void makeEmpty( );
private:
  int currentSize; // Number of elements in heap
  vector array; // The heap array
  void buildHeap( );
  void percolateDown( int hole );
};
#endif

BinaryHeap.cpp

#include “BinaryHeap.h”
/**
* Construct the binary heap.
* capacity is the capacity of the binary heap.
*/
template BinaryHeap::BinaryHeap( int capacity )
  : array( capacity + 1 ), currentSize( 0 )
{
}

/**
* Insert item x into the priority queue, maintaining heap order.
* Duplicates are allowed.
* Throw Overflow if container is full.
*/
template void BinaryHeap::insert( const Comparable & x )
{
  if( isFull( ) )
    throw Overflow( );
  // Percolate up
  int hole = ++currentSize;
  for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 )
    array[ hole ] = array[ hole / 2 ];
  array[ hole ] = x;
}

/**
* Find the smallest item in the priority queue.
* Return the smallest item, or throw Underflow if empty.
*/
template const Comparable & BinaryHeap::findMin( ) const
{
  if( isEmpty( ) )
    throw Underflow( );
  return array[ 1 ];
}

/**
* Remove the smallest item from the priority queue.
* Throw Underflow if empty.
*/
template void BinaryHeap::deleteMin( )
{
  if( isEmpty( ) )
    throw Underflow( );
  array[ 1 ] = array[ currentSize-- ];
  percolateDown( 1 );
}

/**
* Remove the smallest item from the priority queue
* and place it in minItem. Throw Underflow if empty.
*/
template void BinaryHeap::deleteMin( Comparable & minItem )
{
  if( isEmpty( ) )
    throw Underflow( );
  minItem = array[ 1 ];
  array[ 1 ] = array[ currentSize-- ];
  percolateDown( 1 );
}

/**
* Establish heap order property from an arbitrary
* arrangement of items. Runs in linear time.
*/
template void BinaryHeap::buildHeap( )
{
  for( int i = currentSize / 2; i > 0; i– )
    percolateDown( i );
}

/**
* Test if the priority queue is logically empty.
* Return true if empty, false otherwise.
*/
template bool BinaryHeap::isEmpty( ) const
{
  return currentSize == 0;
}

/**
* Test if the priority queue is logically full.
* Return true if full, false otherwise.
*/
template bool BinaryHeap::isFull( ) const
{
  return currentSize == array.size( ) – 1;
}

/**
* Make the priority queue logically empty.
*/
template void BinaryHeap::makeEmpty( )
{
  currentSize = 0;
}

/**
* Internal method to percolate down in the heap.
* hole is the index at which the percolate begins.
*/
template void BinaryHeap::percolateDown( int hole )
{
/* 1*/ int child;
/* 2*/ Comparable tmp = array[ hole ];
/* 3*/ for( ; hole * 2 <= currentSize; hole = child )
       {
/* 4*/   child = hole * 2;
/* 5*/   if( child != currentSize && array[ child + 1 ] < array[ child ] )
/* 6*/     child++;
/* 7*/   if( array[ child ] < tmp )
/* 8*/     array[ hole ] = array[ child ];
         else
/* 9*/     break;
        }
/*10*/  array[ hole ] = tmp;
}

TestBinaryHeap.cpp

#include
#include “BinaryHeap.h”
#include “dsexceptions.h”
// Test program
int main( )
{
  int numItems = 10000;
  BinaryHeap h( numItems );
  int i = 37;
  int x;

  try {
    for( i = 37; i != 0; i = ( i + 37 ) % numItems )
      h.insert( i );

    for( i = 1; i < numItems; i++ )  {
      h.deleteMin( x );
      if( x != i )
        cout << “Oops! ” << i << endl;
    }

    for( i = 37; i != 0; i = ( i + 37 ) % numItems )
      h.insert( i );

    h.insert( 0 );
    h.insert( i = 999999 ); // Should overflow
  } catch( Overflow ) { 
    cout << “Overflow (expected)! ” << i << endl; 
  }
  return 0;
}

Q: Implement Binary Search Tree in C++?
A:
BinarySearchTree.h

#ifndef BINARY_SEARCH_TREE_H_
#define BINARY_SEARCH_TREE_H_
#include “dsexceptions.h”
#include // For NULL
// Binary node and forward declaration because g++ does
// not understand nested classes.
template class BinarySearchTree;
template class BinaryNode
{
  Comparable element;
  BinaryNode *left;
  BinaryNode *right;

  BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
    : element( theElement ), left( lt ), right( rt ) { }

  friend class BinarySearchTree;
};

// BinarySearchTree class
//
// CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) –> Insert x
// void remove( x ) –> Remove x
// Comparable find( x ) –> Return item that matches x
// Comparable findMin( ) –> Return smallest item
// Comparable findMax( ) –> Return largest item
// boolean isEmpty( ) –> Return true if empty; else false
// void makeEmpty( ) –> Remove all items
// void printTree( ) –> Print tree in sorted order
template class BinarySearchTree
{
public:
  explicit BinarySearchTree( const Comparable & notFound );
  BinarySearchTree( const BinarySearchTree & rhs );
  ~BinarySearchTree( );

  const Comparable & findMin( ) const;
  const Comparable & findMax( ) const;
  const Comparable & find( const Comparable & x ) const;
  bool isEmpty( ) const;
  void printTree( ) const;
  void makeEmpty( );
  void insert( const Comparable & x );
  void remove( const Comparable & x );
  const BinarySearchTree & operator=( const BinarySearchTree & rhs );

private:
  BinaryNode *root;
  const Comparable ITEM_NOT_FOUND;
  const Comparable & elementAt( BinaryNode *t ) const;
  void insert( const Comparable & x, BinaryNode * & t ) const;
  void remove( const Comparable & x, BinaryNode * & t ) const;
  BinaryNode * findMin( BinaryNode *t ) const;
  BinaryNode * findMax( BinaryNode *t ) const;
  BinaryNode * find( const Comparable & x, BinaryNode *t ) const;
  void makeEmpty( BinaryNode * & t ) const;
  void printTree( BinaryNode *t ) const;
  BinaryNode * clone( BinaryNode *t ) const;
};
#endif

BinarySearchTree.cpp

#include “BinarySearchTree.h”
#include
/**
* Implements an unbalanced binary search tree.
* Note that all “matching” is based on the < method.
*/

/**
* Construct the tree.
*/
template BinarySearchTree::BinarySearchTree( const Comparable & notFound ) 
  : root( NULL ), ITEM_NOT_FOUND( notFound )
{
}

/**
* Copy constructor.
*/
template BinarySearchTree::BinarySearchTree( const BinarySearchTree & rhs )
  : root( NULL ), ITEM_NOT_FOUND( rhs.ITEM_NOT_FOUND )
{
  *this = rhs;
}

/**
* Destructor for the tree.
*/
template BinarySearchTree::~BinarySearchTree( )
{
  makeEmpty( );
}

/**
* Insert x into the tree; duplicates are ignored.
*/
template void BinarySearchTree::insert( const Comparable & x )
{
  insert( x, root );
}

/**
* Remove x from the tree. Nothing is done if x is not found.
*/
template void BinarySearchTree::remove( const Comparable & x )
{
  remove( x, root );
}

/**
* Find the smallest item in the tree.
* Return smallest item or ITEM_NOT_FOUND if empty.
*/
template const Comparable & BinarySearchTree::findMin( ) const
{
  return elementAt( findMin( root ) );
}

/**
* Find the largest item in the tree.
* Return the largest item of ITEM_NOT_FOUND if empty.
*/
template const Comparable & BinarySearchTree::findMax( ) const
{
  return elementAt( findMax( root ) );
}

/**
* Find item x in the tree.
* Return the matching item or ITEM_NOT_FOUND if not found.
*/
template const Comparable & BinarySearchTree::find( const Comparable & x ) const
{
  return elementAt( find( x, root ) );
}

/**
* Make the tree logically empty.
*/
template void BinarySearchTree::makeEmpty( )
{
  makeEmpty( root );
}

/**
* Test if the tree is logically empty.
* Return true if empty, false otherwise.
*/
template bool BinarySearchTree::isEmpty( ) const
{
  return root == NULL;
}

/**
* Print the tree contents in sorted order.
*/
template void BinarySearchTree::printTree( ) const
{
  if( isEmpty( ) )
    cout << “Empty tree” << endl;
  else
    printTree( root );
}

/**
* Deep copy.
*/
template const BinarySearchTree & BinarySearchTree::operator=( const BinarySearchTree & rhs )
{
  if( this != &rhs )  {
    makeEmpty( );
    root = clone( rhs.root );
  }
  return *this;
}

/**
* Internal method to get element field in node t.
* Return the element field or ITEM_NOT_FOUND if t is NULL.
*/
template const Comparable & BinarySearchTree::elementAt( BinaryNode *t ) const
{
  if( t == NULL )
     return ITEM_NOT_FOUND;
  else
    return t->element;
}

/**
* Internal method to insert into a subtree.
* x is the item to insert.
* t is the node that roots the tree.
* Set the new root.
*/
template void BinarySearchTree::insert( const Comparable & x, BinaryNode * & t ) const
{
  if( t == NULL )
    t = new BinaryNode( x, NULL, NULL );
  else if( x < t->element )
    insert( x, t->left );
  else if( t->element < x )
    insert( x, t->right );
  else
    ; // Duplicate; do nothing
}

/**
* Internal method to remove from a subtree.
* x is the item to remove.
* t is the node that roots the tree.
* Set the new root.
*/
template void BinarySearchTree::remove( const Comparable & x, BinaryNode * & t ) const
{
  if( t == NULL )
    return; // Item not found; do nothing

  if( x < t->element )
    remove( x, t->left );
  else if( t->element < x )
    remove( x, t->right );
  else if( t->left != NULL && t->right != NULL ) // Two children
  {
    t->element = findMin( t->right )->element;
    remove( t->element, t->right );
  }
  else
  {
    BinaryNode *oldNode = t;
    t = ( t->left != NULL ) ? t->left : t->right;
    delete oldNode;
  }
}

/**
* Internal method to find the smallest item in a subtree t.
* Return node containing the smallest item.
*/
template BinaryNode * BinarySearchTree::findMin( BinaryNode *t ) const
{
  if( t == NULL )
    return NULL;

  if( t->left == NULL )
    return t;

  return findMin( t->left );
}

/**
* Internal method to find the largest item in a subtree t.
* Return node containing the largest item.
*/
template BinaryNode * BinarySearchTree::findMax( BinaryNode *t ) const
{
  if( t != NULL )
    while( t->right != NULL )
      t = t->right;

  return t;
}

/**
* Internal method to find an item in a subtree.
* x is item to search for.
* t is the node that roots the tree.
* Return node containing the matched item.
*/
template BinaryNode * BinarySearchTree::find( const Comparable & x, BinaryNode *t ) const
{
  if( t == NULL )
    return NULL;
  else if( x < t->element )
    return find( x, t->left );
  else if( t->element < x )
    return find( x, t->right );
  else
    return t; // Match
}

/****** NONRECURSIVE VERSION*************************
template BinaryNode * BinarySearchTree::find( const Comparable & x, BinaryNode *t ) const
{
  while( t != NULL )
    if( x < t->element )
      t = t->left;
    else if( t->element < x )
      t = t->right;
    else
      return t; // Match

  return NULL; // No match
}
*****************************************************/

/**
* Internal method to make subtree empty.
*/
template void BinarySearchTree::makeEmpty( BinaryNode * & t ) const
{
  if( t != NULL )  {
    makeEmpty( t->left );
    makeEmpty( t->right );
    delete t;
  }
  t = NULL;
}

/**
* Internal method to print a subtree rooted at t in sorted order.
*/
template void BinarySearchTree::printTree( BinaryNode *t ) const
{
  if( t != NULL )  {
    printTree( t->left );
    cout << t->element << endl;
    printTree( t->right );
  }
}

/**
* Internal method to clone subtree.
*/
template BinaryNode * BinarySearchTree::clone( BinaryNode * t ) const
{
  if( t == NULL )
    return NULL;
  else
    return new BinaryNode( t->element, clone( t->left ), clone( t->right ) );
}

#include “BinarySearchTree.h”
// Test program
int main( )
{
  const int ITEM_NOT_FOUND = -9999;
  BinarySearchTree t( ITEM_NOT_FOUND );
  int NUMS = 4000;
  const int GAP = 37;
  int i;

  cout << “Checking… (no more output means success)” << endl;

  for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
    t.insert( i );

  for( i = 1; i < NUMS; i+= 2 )
    t.remove( i );

  if( NUMS < 40 )
    t.printTree( );

  if( t.findMin( ) != 2 || t.findMax( ) != NUMS – 2 )
    cout << “FindMin or FindMax error!” << endl;

  for( i = 2; i < NUMS; i+=2 )
    if( t.find( i ) != i )
      cout << “Find error1!” << endl;

  for( i = 1; i < NUMS; i+=2 )
  {
    if( t.find( i ) != ITEM_NOT_FOUND )
       cout << “Find error2!” << endl;
  }

  BinarySearchTree t2( ITEM_NOT_FOUND );
  t2 = t;
  for( i = 2; i < NUMS; i+=2 )
    if( t2.find( i ) != i )
       cout << “Find error1!” << endl;

  for( i = 1; i < NUMS; i+=2 )
  {
    if( t2.find( i ) != ITEM_NOT_FOUND )
      cout << “Find error2!” << endl;
  }

  return 0;
}

the end